Recent experiments have convincingly demonstrated the existence of surface nanobubbles on submerged hydrophobic surfaces. However, classical theory dictates that small gaseous bubbles quickly dissolve because their large Laplace pressure causes a diffusive outflux of gas. Here we suggest that the bubbles are stabilized by a continuous influx of gas near the contact line, due to the gas attraction towards hydrophobic walls [Dammer and Lohse, Phys. Rev. Lett. 96, 206101 (2006); Zhang et al., Phys. Rev. Lett. 98, 136101 (2007); Mezger et al., J. Chem. Phys. 128, 244705 (2008)]. This influx balances the outflux and allows for a metastable equilibrium, which, however, vanishes in thermodynamic equilibrium. Our theory predicts the equilibrium radius of the surface nanobubbles, as well as the threshold for surface nanobubble formation as a function of hydrophobicity and gas concentration.