Rechargeable magnesium batteries (RMBs) have attracted increasing attention as promising next-generation energy storage systems owing to their high safety and the natural abundance of magnesium resources. However, their large-scale commercialization remains hindered by critical challenges, including the limited selection of suitable electrode materials and the insufficient performance of electrolytes. In this study, motivated by the excellent structural rigidity and minimal volume variation of titanium-based materials during charge–discharge processes, a pseudo-brookite MgTi2O5 compound was synthesized via a sol–gel method as a novel cathode material for RMBs. The optimal synthesis parameters were systematically identified by tuning the Mg/Ti molar ratio of the precursors, as well as the temperature and time of heat treatment. Furthermore, a thin carbon coating with a thickness of approximately 1 nm was introduced onto the surface of MgTi2O5 via a carbon-coating strategy to enhance its electrochemical performance. At a current density of 50 mA g−1, MgTi2O5 exhibits an initial discharge capacity of 68.94 mAh g−1, while maintaining a high capacity retention of 79.14% after 1000 cycles at a high current density of 500 mA g−1. This study reveals that the charge compensation during the charge–discharge process of MgTi2O5 is mainly contributed by the Ti3+/Ti4+ redox pair. Our findings validate the feasibility of using MgTi2O5 as a cathode material in RMBs, providing valuable insights for the development of novel titanium-based electrode materials for magnesium batteries.