Ultrafine niobium oxide nanocrystals/reduced graphene oxide (Nb<sub>2sub>O<sub>5sub> NCs/rGO) was demonstrated as a promising anode material for sodium ion battery with high rate performance and high cycle durability. Nb<sub>2sub>O<sub>5sub> NCs/rGO was synthesized by controllable hydrolysis of niobium ethoxide and followed by heat treatment at 450 °C in flowing forming gas. Transmission electron microscopy images showed that Nb<sub>2sub>O<sub>5sub> NCs with average particle size of 3 nm were uniformly deposited on rGO sheets and voids among Nb<sub>2sub>O<sub>5sub> NCs existed. The architecture of ultrafine Nb<sub>2sub>O<sub>5sub> NCs anchored on a highly conductive rGO network can not only enhance charge transfer and buffer the volume change during sodiation/desodiation process but also provide more active surface area for sodium ion storage, resulting in superior rate and cycle performance. Ex situ XPS analysis revealed that the sodium ion storage mechanism in Nb<sub>2sub>O<sub>5sub> could be accompanied by Nb<sup>5+sup>/Nb<sup>4+sup> redox reaction and the ultrafine Nb<sub>2sub>O<sub>5sub> NCs provide more surface area to accomplish the redox reaction.