A new solvothermal strategy combined with calcination has been developed to synthesize NaTi2(PO4)3-graphene nanocomposites. X-ray diffraction, thermogravimetric analysis, field-emission scanning electron microscopy and transmission electron microscopy were performed to characterize their microstructures and morphologies. It was found that NASICON-type structured NaTi2(PO4)3 nanoparticles with highly crystallinity were homogeneously anchored on the surface of conducting graphene nanosheets, forming a two-dimensional hybrid nanoarchitecture. A possible growth mechanism was also discussed based on time-dependent experiments. When used as anode materials for Na-ion batteries, the nanocomposites exhibited excellent electrochemical performance with high-rate capability and excellent cycling stability in 1 M Na2SO4 aqueous electrolyte. The electrode delivered high specific capacities of 110, 85, 65, 40 mA h g(-1) at 2, 5, 10 and 20 C, respectively, and still retained 90% of the initial capacity after 100 cycles at 2 C.