We show that the distribution of nanobubbles is inhomogeneous on the (under-water) surface of highly orientated pyrolytic graphite (HOPG), reflecting the atomic steps: The formation of nanobubbles is strongly enhanced at the upper side of the atomic steps, i.e., the most hydrophobic area on the surface. In contrast, no nanobubbles are formed at the lower side of the steps, i.e., the most hydrophilic area. The width of this nanobubble-free zone is approximately 20 nm. We thus establish a correlation between surface topography and nanobubble formation. In addition, we show that the profile of nanobubbles is sensitive to the applied AFM tip-force, demonstrating the deformability of nanobubbles.