MgMn2O4 spinel oxide has a very positive redox potential (2–3 V vs. Mg/Mg2+) and is a promising positive electrode material for Mg rechargeable batteries. However, the charge of MgMn2O4 cannot be adequately accumulated due to oxidative electrolyte decomposition resulting in poor cyclability. We have examined the effect of transition metal ion substitution in Mg spinel oxides and demonstrated that oxidative electrolyte decomposition is suppressed by replacing Mn cations in MgMn2O4 with Fe. Tetragonal MgMn2O4 spinel was converted into cubic-phase Mg(Mn1−xFex)2O4, when 20% or more of its Mn3+ ions were replaced by Fe3+ (x = 0.2, 0.4, 0.6, 0.8, 1). Mixed Mn–Fe cubic spinel oxides exhibited enhanced cyclic performance due to the suppression of oxidative electrolyte decomposition and improved structural stability. This approach provides a means of improving the electrochemical performance of Mg battery systems without requiring thermodynamically stable electrolytes.