The discovery of new anode materials and engineering their fine structures are the core elements in the development of new-generation lithium ion batteries (LIBs). To this end, we herein report a novel nanostructured composite consisting of approximately 75% Fe3O4 nanorods and 25% reduced graphene oxide (rGO). Microscopy and spectroscopy analyses have identified that the Fe3O4 nanorods are wrapped (or encapsulated) by the rGO nanosheets via covalent bonding, which further self-assemble into a mesoporous hybrid composite networked by the graphene matrix. The composite has an average pore size around 20 nm and exhibits a high surface area of 152 m2 g−1, which is 76 times as high as that of conventional Fe3O4 powder. We have used the composite as an LIB anode material to fabricate coin-type prototype cells with lithium as the cathode. Systematic half-cell testing evaluations show that the electrochemical performance of the present composite material is amongst the best of the transition metal-oxide based LIB anode materials. The performances are characterized by a high reversible capacity of 1053 mA h g−1 subjected to 250 charge–discharge cycles at 500 mA g−1 and an excellent rate capability with the deliverable energy of 788–541 mA h g−1 upon the application of high current densities of 1000–5000 mA g−1. Overall, we have demonstrated that Fe3O4 nanorod–rGO hybrid composite is an interesting and promising material for the fabrication of LIB anodes.