A facile one pot hydrothermal method has been developed to synthesize laminate-structured graphene sheet–Fe3O4 nanocomposites (GNS–Fe3O4). Fe3O4 nanoparticles were decorated densely and homogeneously in the graphene matrix. Galvanostatic charge–discharge cycling of the GNS–Fe3O4 nanocomposites exhibited a reversible specific capacity over 1200 mAh g−1 at 100 mA g−1 without palpable fading for 50 cycles in the voltage range 0.01–3.0 V. A cell for the rate capacity test indicated a high current density of 946 mAh g−1 at a cycling rate of 1000 mA g−1, which could be fully recovered to 1359 mAh g−1 at 100 mA g−1 after 50 cycles. The superior electrochemical performance of the nanocomposites can be attributed to the following factors: (i) the thermal expanded graphene oxide (TEGO) under atmosphere could attach more oxygen functional groups than the hydrogen reduced graphene, which benefited the adsorption and fastness of the nano-sized Fe3O4; (ii) annealing of TEGO–Fe3O4 nanocomposites further improved the conductivity of the graphene matrix, providing a high electron transport rate at the electrode–electrolyte interface; (iii) the laminated structure of nanocomposites could prevent the agglomeration of Fe3O4 nanoparticles and the restacking of graphene sheets, and effectively release the strain caused by the volume expansion of the Fe3O4 nanoparticles, facilitating ion/electron transportation within the electrode and at the electrode–electrolyte interface.