A major challenge in the development of rechargeable Li-O2 batteries is the identification of electrolyte materials that are stable in the operating environment of the O2 electrode. Straight-chain alkyl amides are one of the few classes of polar, aprotic solvents that resist chemical degradation in the O2 electrode, but these solvents do not form a stable solid-electrolyte interphase (SEI) on the Li anode. The lack of a persistent SEI leads to rapid and sustained solvent decomposition in the presence of Li metal. In this work, we demonstrate for the first time successful cycling of a Li anode in the presence of the solvent, N,N-Dimethylacetamide (DMA), by employing a salt, lithium nitrate (LiNO3), that stabilizes the SEI. A Li-O2 cell containing this electrolyte composition is shown to cycle for more than 2000 hours (>80 cycles) at a current density of 0.1 mA/cm2 with a consistent charging profile, good capacity retention and O2 detected as the primary gaseous product formed during charging. The discovery of an electrolyte system that is compatible with both electrodes in a Li-O2 cell may eliminate the need for protecting the anode with a ceramic membrane.