Rechargeable batteries using multivalent metals are among the most promising next-generation battery systems due to their high capacity, high safety, and low cost compared with lithium-ion batteries. However, strong cation-anion interaction degrades diffusion in solid cathodes, an effect that must be mitigated to yield practical multivalent metal batteries. We show that a highly defective iron phosphate-carbon composite prepared by ultracentrifugation serves as a reversible insertion/deinsertion for magnesium ions with, and operates beyond, a 2-V cell voltage at room temperature. A composite of noncrystalline particles that embeds the surrounding carbon structure enhances the magnesium-ion diffusion in the solid phase with stability for cycle life. X-ray absorption spectroscopy, transmission electron microscopy with energy-dispersive X-ray spectroscopy, and high-energy X-ray scattering measurements demonstrate magnesium-ion insertion and extraction in the defective iron phosphate without conversion reactions. This work suggests promising applications for highly defective structures as intercalation hosts for multivalent ions.