The lithium storage capabilities of ultra-fine rutile TiO2 nanoparticles have been studied. Ultra-fine rutile TiO2 nanoparticles with only several nanometers in size have been prepared by a modified wet-chemical method with a high yield. Unexpectedly, the rutile TiO2 nanoparticles with 3nm in size exhibit superior lithium storage properties. Specifically, they show long term cycling stability upon extended cycling for at least 300 cycles with a capacity loss of only 0.17% per cycle, and good rate capability up to a 30C rate. The excellent reversible lithium storage capabilities could be attributed to the ultra-fine size giving rise to a very short diffusion path, and the relatively large surface area which provides more sites for lithium insertion.