High-resolution temperature-dependent photoemission data from Na 2p core levels reveal substantially larger phonon broadening in the first atomic layer of Na(110) than in the bulk. We show that the enhanced width is due primarily to the excitation of relatively soft phonon modes perpendicular to the surface. Soft surface-phonon modes also account for previously reported but uninterpreted broadening of transition-metal surface-atom core levels.