Metal-air batteries are thought to be the ultimate solution for energy storage systems owing to their high energy density. Here we report a long-life Na-O2 battery with a high capacity of 750 mA h g(carbon)(-1) by manipulating the nucleation and growth of nano-sized NaO2 particles in a vertically aligned carbon nanotubes (VACNTs) network with a large surface area. Benefiting from the kinetically favorable formation of NaO2 reaction with a low overpotential of ~0.2 V, the electrical energy efficiency is as high as 90% for up to 100 cycles. A good rate performance (~1500 mA h g(carbon)(-1) at 667 mA g(carbon)(-1)) can be achieved through pre-deposition of a thin NaO2 layer. This study encourages the exploration of the key factors influencing the performance of metal-air batteries, as well as Na-based batteries characterized by phase transformation or conversion reactions.