In single unit-cell FeSe grown on SrTiO3, the superconductivity transition temperature features a significant enhancement. Local phonon modes at the interface associated with electron-phonon coupling may play an important role in the interface-induced enhancement. However, such phonon modes have eluded direct experimental observations. Indeed, the complicated atomic structure of the interface brings challenges to obtain the accurate structure-phonon relation knowledge from either experiment or theory, thus hindering our understanding of the enhancement mechanism. Here, we achieve direct characterizations of atomic structure and phonon modes at the FeSe/SrTiO3 interface with atomically resolved imaging and electron energy loss spectroscopy in a scanning transmission electron microscope. We find several phonon modes highly localized (~1.3 nm) at the unique double layer Ti-O termination at the interface, one of which (~ 83 meV) engages in strong interactions with the electrons in FeSe based on ab initio calculations. The electron-phonon coupling strength for such a localized interface phonon with short-range interactions is comparable to that of Fuchs-Kliewer (FK) phonon mode with long-rang interactions. Thus, our atomic-scale study provides new insights into understanding the origin of superconductivity enhancement at the FeSe/SrTiO3 interface.