In the search for room-temperature batteries with high energy densities, rechargeable metal-air (more precisely metal-oxygen) batteries are considered as particularly attractive owing to the simplicity of the underlying cell reaction at first glance. Atmospheric oxygen is used to form oxides during discharging, which-ideally-decompose reversibly during charging. Much work has been focused on aprotic Li-O(2) cells (mostly with carbonate-based electrolytes and Li(2)O(2) as a potential discharge product), where large overpotentials are observed and a complex cell chemistry is found. In fact, recent studies evidence that Li-O(2) cells suffer from irreversible electrolyte decomposition during cycling. Here we report on a Na-O(2) cell reversibly discharging/charging at very low overpotentials (< 200 mV) and current densities as high as 0.2 mA cm(-2) using a pure carbon cathode without an added catalyst. Crystalline sodium superoxide (NaO(2)) forms in a one-electron transfer step as a solid discharge product. This work demonstrates that substitution of lithium by sodium may offer an unexpected route towards rechargeable metal-air batteries.