A nanocomposite of Mn3O4 wrapped in graphene sheets (GSs) was successfully synthesized via a facile, effective, energy-saving, and scalable microwave hydrothermal technique. The morphology and microstructures of the fabricated GS–Mn3O4 nanocomposite were characterized using various techniques. The results indicate that the particle size of the Mn3O4 particles in the nanocomposite markedly decreased to nearly 20 nm, significantly smaller than that for the bare Mn3O4. Electrochemical measurements demonstrated a high specific capacity of more than 900 mA h g−1 at 40 mA g−1, and excellent cycling stability with no capacity decay can be observed up to 50 cycles. All of these properties are also interpreted by experimental studies and theoretical calculations.