We report direct angle-resolved photoemission measurements of the coupling between the symmetric stretch vibrational mode of adsorbed hydrogen and a surface band on W(110). This coupling is manifested by the surface band being split into two branches at a binding energy comparable to the vibrational mode energy, as confirmed by observation of a dramatic hydrogen/deuterium isotope effect. The electron-phonon coupling parameter lambda is found to be significantly larger than that for bulk W, and to be closely related to the degree of surface localization of the surface state wave function.