Growing global demand of safe and low-cost energy storage technology triggers strong interests in novel battery concepts beyond state-of-art Li-ion batteries. Here we report a high-voltage rechargeable Mg–Na hybrid battery featuring dendrite-free deposition of Mg anode and Na-intercalation cathode as a low-cost and safe alternative to Li-ion batteries for large-scale energy storage. A prototype device using a Na3V2(PO4)3 cathode, a Mg anode, and a Mg–Na dual salt electrolyte exhibits the highest voltage (2.60V vs. Mg) and best rate performance (86% capacity retention at 10C rate) among reported hybrid batteries. Synchrotron radiation-based X-ray absorption near edge structure (XANES), atomic-pair distribution function (PDF), and high-resolution X-ray diffraction (HRXRD) studies reveal the chemical environment and structural change of Na3V2(PO4)3 cathode during the Na ion insertion/deinsertion process. XANES study shows a clear reversible shift of vanadium K-edge and HRXRD and PDF studies reveal a reversible two-phase transformation and V–O bond length change during cycling. The energy density of the hybrid cell could be further improved by developing electrolytes with a higher salt concentration and wider electrochemical window. This work represents a significant step forward for practical safe and low-cost hybrid batteries.