Solvent plays a major role in determining the nature of discharge products and the extent of rechargeability of the nonaqueous lithium-air (oxygen) battery. Here we investigate chemical stability for a number of aprotic solvents against superoxide, including N,N-dialkyl amides, aliphatic and aromatic nitriles, oxygenated phosphorus (V) compounds, substituted 2-oxazolidinones, and fluorinated ethers. The free energy barriers for nucleophilic attack by superoxide and the C-H acidity constants in dimethyl sulfoxide are reported, which provide a theoretical framework for computational screening of stable solvents for Li-air batteries. Theoretical results are complemented by cyclic voltammetry to study the electrochemical reversibility of the O2/O2− couple containing tetrabutylammonium salt and GCMS measurements to monitor solvent stability in the presence of KO2 and a Li salt. Excellent agreement among all quantum chemical, electrochemical, and chemical methods has been obtained in evaluating solvent stability against superoxide. The combined theoretical and experimental methodology provides a comprehensive testing ground to identify electrolyte solvents stable in the air cathode. Based upon this knowledge we report on the use of an amide-based electrolyte for rechargeable oxygen electrodes in Li-O2 secondary cells.