The possibility of underwater superhydrophobicity is theoretically analyzed. Thermodynamic equilibrium and stability conditions are formulated, and the design goal is defined as minimizing the solid-liquid contact area. It is shown that for sufficiently high roughness ratios, underwater superhydrophobicity may be feasible and thermodynamically stable. In addition, some generic design optimization considerations are demonstrated.