In this work, MgxFePO4 is exploited as a cathode material for rechargeable Mg-ion batteries. FePO4/C prepared via electrochemical delithiation of LiFePO4/C is directly used as the cathode in aqueous Mg2+ electrolyte, and reversible capacity is achieved for the first time. Notably, the capacity (82 mA h/g) is half of the theoretical value (164 mA h/g) and "asymmetric" discharge/charge behavior can be observed. In addition, first principles calculations show it is the strong Mg-ion interactions between adjacent channels that not only limit the capacity of the cathode but also lead to the difference in rates for Mg-ion intercalation and deintercalation. This work provides experimental and theoretical evidence that reveal the mechanism of Mg-ion intercalation and deintercalation in a FePO4 host, which gives guidance in designing cathode materials for rechargeable batteries based on multivalent metal ions.