We describe a new strategy to increase charge storage in a dual electrolyte Na-ion battery (DESIB) by combining the redox chemistry of the electrolyte with a Na+ ion de-insertion/insertion cathode. Conventional electrolytes do not contribute to charge storage in battery systems, but redox-active electrolytes augment this property via charge transfer reactions at the electrode-electrolyte interface. Hence, the capacity of the cathode combined with that provided by the electrolyte redox reaction increases overall charge storage. We employ an aqueous sodium hexacyanoferrate (Na4Fe(CN)6) solution as the redox-active electrolyte (Na-FC) and sodium nickel Prussian blue (Nax-NiBP) as the Na+ ion insertion/de-insertion cathode. The capacity of DESIB with Na-FC electrolyte is twice that of a battery using conventional (Na2SO4) electrolyte. The use of redox-active electrolytes in batteries of any kind is an efficient and scalable approach to develop advanced high-energy-density storage systems.