We report on the first ab initio study of the electron–phonon interaction and its contribution to the lifetime broadening of excited hole (electron) surface states on the (110) surface of Ag and Cu. The calculations based on density-functional theory were carried out using a linear response approach in the mixed-basis pseudopotential representation. The calculated strength of the phonon-mediated scattering varies with the energy position of a hole (electron) state in the surface energy band while a directional anisotropy is noticeable only for occupied surface states. It is shown that the electron–phonon interaction in occupied surface states is largely determined by bulk electronic states and is weak compared to the phonon-induced coupling of excited electrons, characterized by a strong energy dependence due to significant intraband scattering. Analysis of various contributions to the electron–phonon coupling reveals that the bulk phonon modes determine the scattering of excited holes, while the surface phonon modes are more involved in the coupling of exited electrons.