We present a comprehensive theoretical investigation of the electron-phonon contribution to the lifetime broadening of the surface states on Cu(111) and Ag(111), in comparison with high-resolution photoemission results. The calculations, including electron and phonon states of the bulk and the surface, resolve the relative importance of the Rayleigh mode, being dominant for the lifetime at small hole binding energies. Including the electron-electron interaction, the theoretical results are in excellent agreement with the measured binding energy and temperature dependent lifetime broadening.