Spherical-cap-shaped interfacial nanobubbles (NBs) forming on hydrophobic surfaces in aqueous solutions have extensively been studied both from a fundamental point of view and due to their relevance for various practical applications. In this study, the nucleation mechanism of spontaneously generated NBs at solid-liquid interfaces of immersed nanostructured hydrophobic surfaces is studied. Depending on the size and density of the surface nanostructures, NBs with different size and density were reproducibly and deterministically obtained. A two-step process can explain the NB nucleation, based on the crevice model, i.e., entrapped air pockets in surface cavities which grow by diffusion. The results show direct evidence for the spontaneous formation of NBs on a surface at its immersion. Next, the influence of size and shape of the nanostructures on the nucleated NBs are revealed. In particular, on non-circular nanopits we obtain NBs with a non-circular footprint, demonstrating the strong pinning forces at the three-phase contact line.