Aprotic metal-oxygen batteries, such as Li-O2 and Na-O2 batteries, are of topical research interest as high specific energy alternatives to state-of-the-art Li-ion batteries. In particular, Na-O2 batteries with NaO2 as the discharge product offer higher practical specific energy with better rechargeability and round-trip energy efficiency when compared to Li-O2 batteries. In this work, we show that the electrochemical deposition and dissolution of NaO2 in Na-O2 batteries is unperturbed by trace water impurities in Na-O2 battery electrolytes, which is desirable for practical battery applications. We find no evidence for the formation of other discharge products such as Na2O2·H2O. Furthermore, the electrochemical efficiency during charge remains near ideal in the presence of trace water in electrolytes. Although sodium anodes react with trace water leading to the formation of a high-impedance solid electrolyte interphase, the increase in discharge overpotential is only ∼100 mV when compared to cells employing nominally anhydrous electrolytes.