Sodium ion batteries attract increasing attention for large-scale energy storage as a promising alternative to the lithium counterparts in view of low cost and abundant sodium source. However, the large ion radius of Na brings about a series of challenging thermodynamic and kinetic difficulties to the electrodes for sodium-storage, including low reversible capacity and low ion transport, as well as large volume change. To mitigate or even overcome the kinetic problems, we develop a self-assembly route to a novel architecture consisting of nanosized porous NASICON-type NaTi2(PO4)3 particles embedded in microsized 3D graphene network. Such architecture synergistically combines the advantages of a 3D graphene network and of 0D porous nanoparticles. It greatly increases the electron/ion transport kinetics and assures the electrode structure integrity, leading to attractive electrochemical performance as reflected by a high rate-capability (112 mAh g–1 at 1C, 105 mAh g–1 at 5C, 96 mAh g–1 at 10C, 67 mAh g–1 at 50C), a long cycle-life (capacity retention of 80% after 1000 cycles at 10C), and a high initial Coulombic efficiency (>79%). This nanostructure design provides a promising pathway for developing high performance NASICON-type materials for sodium storage.