Cost-efficient, high-voltage, stable sodium-based cathodes are needed to develop commercial-scale sodium batteries. In this work, a Na3V2(PO4)3/carbon (NVP@C) composite sodium cathode material is synthesized by a novel, facile, two-step, solid state method. This material delivered a discharge capacity of 115 mAhg-1 at 0.5C rate with a conventional organic electrolyte. Improvements in stable cycling were found when NVP@C was paired with a “hybrid” electrolyte comprising a [50:50] v/v mixture of 1M Sodium bis(fluorosulfonyl)amide (NaFSI) in an organic electrolyte and an ionic liquid, N-methyl-N-propyl pyrrolidinium bis(trifluoromethanesulfonyl)amide(C3mpyrTFSI). Sodium batteries based on NVP@C cathode retained 95% after 100 cycles at 0.5 C rate. We show that the hybrid electrolyte enhanced the electrochemical performance of the NVP@C cathode material by forming a stable SEI (solid-electrolyte interphase) layer on the surface. Electron microscopy and x-ray photoelectron spectroscopy were used to study the SEI layers on electrodes that had been subjected to 100 cycles with hybrid or conventional organic electrolytes. The hybrid electrolyte produced a less resistive, highly Na+ ion permeable SEI layer,explaining its superior sodium battery performance, compared to that found with the conventional organic electrolyte.