Sodium-ion (Na-ion) batteries have been attracting great interest because of a wide range of potential applications and sodium abundance. Yet, the performance of Na-ion electrode materials needs improvement to be able to compete with lithium-ion electrode materials. Here, sodium-vanadium hexacyanoferrate (NaVHCF) is investigated as a cathode active material in rechargeable Na-ion batteries. We explore the electrochemical performance of NaVHCF in a liquid organic electrolyte and demonstrate a high and very stable working potential of around 3.3 V vs Na+/Na, achieving excellent capacity retention of 73% after 200 cycles. Vanadium substitution in a Prussian blue crystal structure can improve the cycle life by acting as a pillar in interstitial spaces. These results represent a step forward in the development of cathode materials for Na-ion batteries.