A promising strategy for increasing the energy density of Li-ion batteries is to substitute a multivalent (MV) metal for the commonly used lithiated carbon anode. Magnesium is a prime candidate for such a MV battery due to its high volumetric capacity, abundance, and limited tendency to form dendrites. One challenge that is slowing the implementation of Mg-based batteries, however, is the development of efficient and stable electrolytes. Computational screening for molecular species having sufficiently wide electrochemical windows is a starting point for the identification of optimal electrolytes. Nevertheless, this window can be altered via interfacial interactions with electrodes. These interactions are typically omitted in screening studies, yet they have the potential to generate large shifts to the HOMO and LUMO of the electrolyte components. The present study quantifies the stability of several common electrolyte solvents on model electrodes of relevance for Mg batteries. Many-body perturbation theory calculations based on the G0W0 method were used to predict shifts in a solvent's electronic levels arising from interfacial interactions. In molecules exhibiting large dipole moments, our calculations indicate that these interactions reduce the HOMO-LUMO gap by ∼25% (compared to isolated molecules). We conclude that electrode interactions can narrow an electrolyte's electrochemical window significantly, thereby accelerating redox decomposition reactions. Accounting for these interactions in screening studies presents an opportunity to refine predictions of electrolyte stability.