Superhydrophobic surfaces are effective in practical applications provided they are “robust superhy-drophobic”, i.e. able to retain the Cassie state, i.e. with water suspended onto the surface protrusions,even under severe conditions (high pressure, vibrations, high speed impact, etc.). We show that for ran-domly rough surfaces, given the Young angle, Cassie states are robust when a threshold value of theWenzel roughness factor, rW, is exceeded. In particular, superhydrophobic nano-textured surfaces havebeen generated by self-masked plasma etching. In view of their random roughness, topography features,acquired by Atomic Force Microscopy, have been statistically analyzed in order to gain information onstatistical parameters such as power spectral density, fractal dimension and Wenzel roughness factor(rW), which has been used to assess Cassie state robustness. Results indicate that randomly rough sur-faces produced by plasma at high power or long treatment duration, which are also fractal self-affine,have a rWhigher than the theoretical threshold, thus for them a robust superhydrophobicity is predicted.In agreement with this, under dynamic wetting conditionson these surfaces the most pronounced super-hydrophobic character has been appreciated: they show the lowest contact angle hysteresis and resultin the sharpest bouncing when hit by drops at high impact velocity.