In this study, we synthesize a carbon-coated Na3V1.96Fe0.04(PO4)3-Fe2P composite (NVFP-FP/C) as a cathode material using a one-pot pyro-synthesis method and demonstrate its superior sodium storage performance for sodium-ion batteries. The Na3V1.96Fe0.04(PO4)3-Fe2P composite consists of unique nanoclusters of electrically conductive ultra-fine Fe2P crystals randomly dispersed among the NVP particles. The presence of Fe2P in the composite cathode greatly enhances its electronic conductivity and Na+-ion diffusion co-efficient; hence, the NVFP-FP/C cathode exhibits a high discharge capacity of 103.2 mAh g−1 at 0.1C, remarkable long term cycling stability over 2000 cycles at 20C and excellent power capability up to 40C.