We observe stable steady-periodic vapor bubble nucleation on islands of nanoscopically smooth hydrophobic materials microfabricated on a silicon substrate. The minimum surface superheat required for the onset of bubble nucleation is very low (similar to 9 degrees C), which cannot be explained by the established models of heterogeneous bubble nucleation. A modified bubble nucleation model indicates that the observed minimum superheat can be explained when one assumes the existence of a nanoscale interfacial gas phase with anomalously high contact angles (>160 degrees). Our data therefore provide independent evidence that supports previous atomic force microscopy and infrared spectroscopy studies of the topography of nanobubbles. (c) 2008 American Institute of Physics.