Magnesium rechargeable batteries using Mg-metal anodes are promising post-lithium-ion batteries. MgMn2O4 is a strong candidate cathode material owing to its high energy density and relatively high Mg2+-ion diffusivity. However, while pristine MgMn2O4 forms a tetragonal spinel structure (I41/amd) owing to the Jahn–Teller effect of Mn3+, it adopts a cubic structure in the charged/discharged state. This results in a structural change from tetragonal to cubic during charge/discharge cycling, leading to poor battery performance and reversibility. To improve the cathode performance, we prepared Al-substituted MgMn2−xAlxO4 spinel (x = 0, 0.1, 0.2, 0.5) to suppress the Jahn–Teller distortion. The obtained MgMn2−xAlxO4 spinel is a two-phase crystal with coexisting tetragonal and cubic spinel structures, whereby the fraction of cubic phase tends to increase with the Al ratio. The Al-substituted spinels exhibit superior discharge capacities to that of MgMn2O4. The increase in cubic spinel phase fraction by Al-substitution and the reduced structural change during discharging will aid the development of superior cathodes for magnesium batteries.