Rough or textured hydrophobic surfaces are dubbed superhydrophobic due to their numerous desirable properties, such as water repellency and interfacial slip. Superhydrophobicity stems from an aversion for water to wet the surface texture, so that a water droplet in the superhydrophobic Cassie state, contacts only the tips of the rough hydrophobic surface. However, superhydrophobicity is remarkably fragile, and can break down due to the wetting of the surface texture to yield the Wenzel state under various conditions, such as elevated pressures or droplet impact. Moreover, due to large energetic barriers that impede the reverse (dewetting) transition, this breakdown in superhydrophobicity is widely believed to be irreversible. Using molecular simulations in conjunction with enhanced sampling techniques, here we show that on surfaces with nanoscale texture, water density fluctuations can lead to a reduction in the free energetic barriers to dewetting by circumventing the classical dewetting pathways. In particular, the fluctuation-mediated dewetting pathway involves a number of transitions between distinct dewetted morphologies, with each transition lowering the resistance to dewetting. Importantly, an understanding of the mechanistic pathways to dewetting and their dependence on pressure, allows us to augment the surface texture design, so that the barriers to dewetting are eliminated altogether and the Wenzel state becomes unstable at ambient conditions. Such robust surfaces, which defy classical expectations and can spontaneously recover their superhydrophobicity, could have widespread importance, from underwater operation to phase change heat transfer applications.