Nanostructured λ-MnO2 and α-MnO2 are investigated for use in rechargeable Mg ion battery (MIB) cathodes. In order to prepare nanosized particles, the manganese dioxides are prepared by the acid treatment of spinel MgMn2O4 synthesized using the Pechini method. X-ray diffraction analysis indicates that the resulting MnO2 consists of multiple phases, λ-MnO2, α-MnO2, and β-MnO2, depending on the leaching time in acid solution. Upon the first charge–discharge cycle in acetonitrile electrolyte, the λ-MnO2 based electrode shows larger reversible capacity of ∼330 mAh g−1 compared to an electrode containing a large amount of α-MnO2. This enhanced capacity is associated with the facile charge-transfer reaction of Mg ions at the MnO2/electrolyte interfaces. The capacity fading of MnO2 in different electrolytes is also discussed in terms of the formation of a surface layer at the electrode/electrolyte interface during the charging process.