The development of Mg batteries, which can potentially achieve higher energy densities than Li-ion systems, is in need of cathodes that can reversibly intercalate Mg2+ and exhibit a higher energy density than the state-of-the-art Chevrel and thio-spinel cathodes. Recent theoretical and experimental studies indicate that the oxide spinel family presents a set of promising Mg cathodes. Specifically, in this work, we investigate Mg intercalation into the spinel-MgxCr2O4 system. Using first-principles calculations in combination with a cluster expansion model and the nudged elastic band theory, we calculate the voltage curve for Mg insertion at room temperature and the activation barriers for Mg diffusion, respectively, at different Mg concentrations in the Cr2O4 structure. Our results identify a potential limitation to Mg intercalation in the form of stable Mg-vacancy orderings in the Cr2O4 lattice, which exhibit high migration barriers for Mg diffusion in addition to a steep voltage change. Additionally, we propose cation substitution as a potential mechanism that can be used to suppress the formation of the stable Mg-vacancy ordering, which can eventually enable the practical usage of Cr2O4 as a Mg-cathode.