A first-principles theory is presented for calculating the lifetime of adsorbate vibrations on semiconductor or insulator surfaces, where dissipation of the vibrational energy to substrate phonons is the dominant relaxation mechanism. As an example, we study the stretching vibration of CO/Si(100), where a lifetime of 2.3 ns has been measured recently [K. Lass, X. Han, and E. Hasselbrink, J. Chem. Phys. 123, 051102 (2005)]. Density-functional theory (DFT) calculations for the local modes of the adsorbate, including their anharmonic coupling, are combined with force field calculations for the substrate phonons. Using the DFT-Perdew-Burke-Ernzerhof functional, we have determined the most stable adsorption site for CO on top of the lower Si atom of the Si surface dimer, the local normal modes of CO, and the multidimensional potential energy surface for the CO vibrations. The anharmonic stretching frequency of adsorbed CO obtained in DFT-PBE is 5% lower than the experimental value, while the B3LYP functional reproduces the CO stretching frequency with only 1.4% error. The coupling between the anharmonic vibrational modes and the phonon continuum is evaluated within first-order perturbation theory, and transition rates for the CO vibrational relaxation are calculated using Fermi's golden rule. The lifetime of 0.5 ns obtained with DFT-PBE is in qualitative agreement with experiment, while using vibrational frequencies from the B3LYP functional gives a much too long lifetime as compared to experiment. We find that the numerical value of the lifetime is very sensitive to the harmonic frequencies used as input to the calculation of the transition rate. An empirical adjustment of these frequencies yields excellent agreement between our theory and experiment. From these calculations we conclude that the most probable microscopic decay channel of the CO stretching mode is into four lateral shift/bending quanta and one phonon.