A simple two-step solid-state-reaction process is adopted to synthesize carbon-coated Mg-doped Li(Mn,Fe)PO4 (LMMFP) nano-particles. As positive electrode materials for lithium-ion batteries, the carbon-coated LMMFP samples show excellent electrochemical properties in a temperature range from −20 to 55 °C. For example, LiMn0.48Fe0.5Mg0.02PO4 can deliver a capacity of 146.2 mAh g−1 at 3C rate and retain 95.3% after 450 cycles at 25 °C. It can also deliver 160.7 mAh g−1 at 1C and retain 97.7% after 100 cycles at 55 °C. Even at −20 °C, it gives a capacity of 109.5 mAh g−1 with an average discharge voltage of 3.37 V at 0.2C. In Na/LMMFP cells, the LMMFP electrodes can be electrochemically converted into Mg-doped Na(Mn,Fe)PO4 (NMMFP) electrodes for sodium-ion batteries (SIBs). Ex-situ XRD proves that the derived NMMFP have an olivine-type structure and can reversibly extract and insert sodium ions. For example, NaMn0.48Fe0.5Mg0.02PO4 can deliver a reversible specific capacity of 126.9 mAh g−1 after 30 cycles at 0.1C with an average discharge voltage of 3.1 V. This study opens up a new direction on exploring olivine-type SIB cathodes.