Advanced anode materials for next generation lithium ion batteries have attracted great interest due to the ever increasing demand for powerful, light-weight, and compact electrical devices. In this work, graphene nanosheets decorated with ultra-small Fe3O4 nanoparticles (USIO/G) were synthesized via a facile hydrothermal method. Compared with other reported Fe3O4-based anode composites, USIO/G demonstrated superior cyclic ability and excellent rate capability owing to its ultra-small size of active lithium storage sites, Fe3O4, with an average diameter less than 5 nm. Furthermore, graphene nanosheets played an important role in the overall electrochemical performance of the composite by enhancing the electrical conductivity, forming a flexible network, and providing extra lithium storage sites. The obtained composites were tested for electrochemical performance for a total number of 2120 cycles: a rate capability test with current densities ranged from 90 to 7200 mA g(-1) for 920 cycles, followed by a cycling test at 1800 mA g(-1) for 1200 cycles. For the rate capability test, steady reversible capacities were delivered under each current density with final reversible capacities of 1177, 1096, 833, 488, 242, and 146 mA h g(-1) at 90, 180, 900, 1800, 3600, and 7200 mA g(-1), respectively. The subsequent cyclic test demonstrated the superior cyclic stability of USIO/G and a reversible capacity of 437 mA h g(-1) at the 2120(th) cycle was delivered.