In this paper, we examine the thermodynamic stability of surface nanobubbles. The appropriate free energy is defined for the system of nanobubbles on a solid surface submerged in a supersaturated liquid solution at constant pressure and temperature, under conditions where an individual nanobubble is not in diffusive contact with a gas phase outside of the system or with other nanobubbles on the time scale of the experiment. The conditions under which plots of free energy versus the radius of curvature of the nanobubbles show a global minimum, which denotes the stable equilibrium state, are explored. Our investigation shows that supersaturation and an anomalously high contact angle (measured through the liquid) are required to have stable surface nanobubbles. In addition, the anomalously high contact angle of surface nanobubbles is discussed from the standpoint of a framework recently proposed by Koch, Amirfazli, and Elliott that relates advancing and receding contact angles to thermodynamic equilibrium contact angles, combined with the existence of a gas enrichment layer.