In this study, Mn3O4 nanocrystals supported by reduced graphene oxide (RGO) nanosheets have been successfully prepared in one step by a facile hydrothermal method. The characterization results show that the well-crystallized Mn3O4 monocrystals are uniformly dispersed on the surface of RGO nanosheets. Further studies indicate that the synergistic effect between RGO nanosheets and Mn3O4 nanocrystals not only alleviates mechanical deformation of the composite but also improves the transport of ions and electrons. As a result, the resulting Mn3O4/RGO nanocomposites deliver a high specific capacity, along with excellent cycle stability and rate performance when used as anode materials for lithium-ion batteries.