Using first-principles calculation, we propose an interface structure for single triple-layer FeSe on the SrTiO3(001) surface, a high-Tc superconductor found recently. The key component of this structure is the oxygen deficiency on the top layer of the SrTiO3 substrate, as a result of Se etching used in preparing the high-Tc samples. The O vacancies strongly bind the FeSe triple layer to the substrate giving rise to a (2 x 1) reconstruction, as observed by scanning tunneling microscopy. The enhanced binding correlates to the significant increase of Tc observed in experiment. The O vacancies also serve as the source of electron doping, which modifies the Fermi surface of the first FeSe layer by filling the hole pocket near the center of the surface Brillouin zone, as suggested from angle-resolved photoemission spectroscopy measurement.