A rechargeable battery based on a multivalent Mg/O2 couple is an attractive chemistry due to its high theoretical energy density and potential for low cost. Nevertheless, metal-air batteries based on alkaline earth anodes have received limited attention and generally exhibit modest performance. In addition, many fundamental aspects of this system remain poorly understood, such as the reaction mechanisms associated with discharge and charging. The present study aims to close this knowledge gap and thereby accelerate the development of Mg/O2 batteries by employing first-principles calculations to characterize electrochemical processes on the surfaces of likely discharge products, MgO and MgO2. Thermodynamic limiting potentials for charge and discharge are calculated for several scenarios, including variations in surface stoichiometry and the presence/absence of intermediate species in the reaction pathway. The calculations indicate that pathways involving oxygen intermediates are preferred, as they generally result in higher discharge and lower charging voltages. In agreement with recent experiments, cells that discharge to MgO exhibit low round-trip efficiencies, which are rationalized by the presence of large thermodynamic overvoltages. In contrast, MgO2-based cells are predicted to be much more efficient: superoxide-terminated facets on MgO2 crystallites enable low overvoltages and round-trip efficiencies approaching 90%. These data suggest that the performance of Mg/O2 batteries can be dramatically improved by biasing discharge toward the formation of MgO2 rather than MgO.