Recent scanning tunneling spectroscopy experiments on graphene reported an unexpected gap of about ±60 meV around the Fermi level [V. W. Brar et al., Appl. Phys. Lett. 91, 122102 (2007); Y. Zhang et al., Nature Phys. 4, 627 (2008)]. Here we give a theoretical investigation explaining the experimentally observed spectra and confirming the phonon-mediated tunneling as the reason for the gap: We study the real space properties of the wave functions involved in the tunneling process by means of ab initio theory and present a model for the electron-phonon interaction, which couples the graphene’s Dirac electrons with quasifree-electron states at the Brillouin zone center. The self-energy associated with this electron-phonon interaction is calculated, and its effects on tunneling into graphene are discussed. Good agreement of the tunneling density of states within our model and the experimental dI/dU spectra is found.