Sodium-ion batteries are emerging as a highly promising technology for large-scale energy storage applications. However, it remains a significant challenge to develop an anode with superior long-term cycling stability and high-rate capability. Here we demonstrate that the Na(+) intercalation pseudocapacitance in TiO2/graphene nanocomposites enables high-rate capability and long cycle life in a sodium-ion battery. This hybrid electrode exhibits a specific capacity of above 90 mA h g(-1) at 12,000 mA g(-1) (∼36 C). The capacity is highly reversible for more than 4,000 cycles, the longest demonstrated cyclability to date. First-principle calculations demonstrate that the intimate integration of graphene with TiO2 reduces the diffusion energy barrier, thus enhancing the Na(+) intercalation pseudocapacitive process. The Na-ion intercalation pseudocapacitance enabled by tailor-deigned nanostructures represents a promising strategy for developing electrode materials with high power density and long cycle life.