The thermodynamic stability of materials can depend on particle size due to the competition between surface and bulk energy. In this Letter, we show that, while sodium peroxide (Na2O2) is the stable bulk phase of Na in an oxygen environment at standard conditions, sodium superoxide (NaO2) is considerably more stable at the nanoscale. As a consequence, the superoxide requires a much lower nucleation energy than the peroxide, explaining why it can be observed as the discharge product in some Na-O2 batteries. As the superoxide can be recharged (decomposed) at much lower overpotentials than the peroxide, these findings are important to create highly reversible Na-O2 batteries. We derive the specific electrochemical conditions to nucleate and retain Na-superoxides and comment on the importance of considering the nanophase thermodynamics when optimizing an electrochemical system.