The complex structure of the Salvinia molesta is investigated via rare event molecular dynamics simulations. Results show that a hydrophilic/hydrophobic patterning together with a re-entrant geometry control the free energy barriers for bubble nucleation and for the Cassie-Wenzel transition. This natural paradigm is translated into simple macroscopic design criteria for engineering robust superhydrophobicity in submerged applications. © 2015 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.