The phonon widths of outermost core-electron photoemission spectra from (110)-oriented overlayers of Na, K, and Rb metals show the expected Debye behavior for the bulk atoms, but significant deviations for the surface atoms. The data indicate a softening of the surface vibrational mode above 200 K. This effect, which is weak in Na but strong in K and Rb, demonstrates that the vibrational mode normal to the surface is anharmonic.