Well-crystallized Mn3O4-anchored reduced graphene oxide (rGO) nanocomposites have been successfully synthesized via a facile, effective, energy-saving, and scalable microwave hydrothermal technique for potential application as supercapacitor material. Integrating these nanostructures resulted in a strong synergistic effect between the two materials, consequently leading to a hybrid composite with higher specific capacitance compared to the bare Mn3O4 nanoparticles. The results from different sorts of characterization indicate that the Mn3O4 particles were deposited and anchored on graphene sheets. The capacitance value of the rGO(31.6%)–Mn3O4 nanocomposite reached 153 F/g, much higher than that of the bare Mn3O4 (87 F/g) at a scan rate of 5 mV/s in the potential range from −0.1 V to 0.8 V. More importantly, a 200% increase in capacitance was observed for the nanocomposite with cycling at 10 mV/s due to electrochemical activation and the oxidization of Mn(II,III) to Mn(IV) during cycling, as verified by Xray photoelectron spectroscopy. There is no observable capacitance fading up to 1000 cycles. The facile synthesis method and good electrochemical properties indicate that the nanocomposite could be an electrode candidate for supercapacitors.