Herein, this study focuses on the design and construction of the reduced graphene oxide (rGO)-Fe3O4 complex, in which nano-sized Fe3O4 particles are evenly decorated on rGO sheets via an electrochemical route as a new efficient approach. Compared to pristine Fe3O4 synthesized without rGO, relatively nano-sized Fe3O4 are obtained by introducing rGO nanosheets. In addition, the synergetic effects of rGO and Fe3O4 effectively enhance the electrochemical conductivity and prevent degradation of the electrode. As a result, the rGO-Fe3O4 composite exhibits a large reversible capacity of 872 mAh g-1 after 100 cycles at 0.1 A g-1, which is considerably higher than pure Fe3O4 and physical mixing of Fe3O4 and rGO. Furthermore, rGO-Fe3O4 composite shows abnormal high capacity over their theoretical value and unusual increase in capacity during the cycle. To investigate this phenomenon, we introduce electrochemical kinetics and ex-situ TEM analysis, concluding that such exceptional capacity is related to both morphological change from spinel to amorphous phase and enhanced interfacial Li ion storage by pseudo-capacitive behavior.