We here describe the extraordinary performance of NASICON Na3V2(PO4)3-carbon nanofiber (NVP-CNF) composites with ultra-high power and excellent cycling performance. NVP-CNFs are composed of CNFs at the center part and partly embedded NVP nanoparticles in the shell. We first report this unique morphology of NVP-CNFs for the electrode material of secondary batteries as well as for general energy conversion materials. Our NVP-CNFs show not only a high discharge capacity of approx. 88.9 mA h g-1 even at a high current density of 50 C but also approx. 93% cyclic retention property after 300 cycles at 1 C. The superb kinetics and excellent cycling performance of the NVP-CNFs are attributed to the facile migration of Na ions through the partly exposed regions of NVP nanoparticles that are directly in contact with an electrolyte as well as the fast electron transfer along the conducting CNF pathways.