We show that the observed repulsive interaction between CO molecules on the Pt(111) surface can be explained by the coupling of the Pt--CO separation with Pt-Pt coordinates in the substrate. The observed long range of the interaction and the non-monotonic distance dependence are reproduced. The magnitude of the multiphonon decay of the Pt--CO vibration calculated in this model is also in agreement with experiment.