Rational design of novel electrolytes with enhanced functionality requires fundamental molecular-level understanding of structure-property relationships. Here we examine the suitability of a range of organic solvents for non-aqueous electrolytes in secondary magnesium batteries using density functional theory (DFT) calculations as well as experimental probes such as cyclic voltammetry and Raman spectroscopy. The solvents considered include ethereal solvents (e.g., glymes) sulfones (e.g., tetramethylene sulfone), and acetonitrile. Computed reduction potentials show that all solvents considered are stable against reduction by Mg metal. Additional computations were carried out to assess the stability of solvents in contact with partially reduced Mg cations (Mg2+ → Mg+) formed during cycling (e.g., deposition) by identifying reaction profiles of decomposition pathways. Most solvents, including some proposed for secondary Mg energy storage applications, exhibit decomposition pathways that are surprisingly exergonic. Interestingly, the stability of these solvents is largely dictated by magnitude of the kinetic barrier to decomposition. This insight should be valuable toward rational design of improved Mg electrolytes.