Rechargeable magnesium batteries (RMBs) are appealing alternatives for energy storage systems based on the high theoretical capacity, low price and high security of the Mg metal anode. Nevertheless, the shortage of high-performance cathode materials severely obstructs its development. As an important conversion material, transition metal selenides, with desirable theoretical capacity and weak bond energy (Mg-Se), have attracted more attention in recent years. In this study, CuFeSe2 (CFS) nanoparticles were produced by a hydrothermal approach and its feasibility as a cathode material for RMBs was further investigated. Given the synergistic effect between Cu and Fe, the optimized CFS shows a reversible capacity of 120 mAh g–1 at 100 mA g–1, outstanding long-term cyclability (86 mAh g–1 at 1A g–1 after 600 cycles), and prominent rate capability (85 mAh g–1 at 1 A g–1). Density functional theory (DFT) computations conclude CFS exhibits a suitable migration barrier for Mg2+ along the tunnel of 0.92 eV. An in-depth investigation of the mechanism demonstrates that the Mg storage process can be divided into solid solution reaction and the conversion processes by ex-situ techniques. This work contributes to further investigate the Mg2+ storage mechanism of cathode materials for RMBs.