Mg/O2 cells employing a MgCl2/AlCl3/DME (MACC/DME) electrolyte are cycled and compared to cells with modified Grignard electrolytes, showing that performance of magnesium/oxygen batteries depends strongly on electrolyte composition. Discharge capacity is far greater for MACC/DME-based cells, while rechargeability in these systems is severely limited. The Mg/O2-MACC/DME discharge product comprises a mixture of Mg(ClO4)2 and MgCl2, with the latter likely formed from slow decomposition of the former. The presence of Cl in these compounds suggests that the electrolyte participates in the cell reaction or reacts readily with the initial electrochemical products. A rate study suggests that O2 diffusion in the electrolyte limits discharge capacities at higher currents. Formation of an insulating product film on the positive electrodes of Mg/O2-MACC/DME cells following deep discharge increases cell impedance substantially and likely explains the poor rechargeability. An additional impedance rise consistent with film formation on the Mg negative electrode suggests the presence of detrimental O2 crossover. Minimizing O2 crossover and bypassing charge transfer through the discharge product would improve battery performance.