The major advantage of Mg batteries relies on their promise of employing an Mg metal negative electrode, which offers much higher energy density compared to graphitic carbon. However, the strong coulombic interaction of Mg2+ ions with anions leads to their sluggish diffusion in the solid state, which along with a high desolvation energy, hinders the development of positive electrode materials. To circumvent this limitation, Mg metal negative electrodes can be used in hybrid systems by coupling an Li+ insertion cathode through a dual salt electrolyte. Two "high voltage" Prussian blue analogues (average 2.3 V vs Mg/Mg2+; 3.0 V vs Li/Li+) are investigated as cathode materials and the influence of structural water is shown. Their electrochemical profiles, presenting two voltage plateaus, are explained based on the two unique Fe bonding environments. Structural water has a beneficial impact on the cell voltage. Capacities of 125 mAh g-1 are obtained at a current density of 10 mA g-1 (≈C/10), while stable performance up to 300 cycles is demonstrated at 200 mA g-1 (≈2C). The hybrid cell design is a step toward building a safe and high density energy storage system.