Mn3O4/graphene nanocomposites with different ratios (M1G1, M1G3 and M3G1) were successfully synthesized by a deposition-solvothermal process. The composites were well characterized with different tools such as TEM-SAED, XRD, FTIR, Raman techniques, and N2 adsorption. The electrochemical characteristics of the nanocomposites were evaluated using cyclic voltammetry (CV), galvanostatic charge-discharge (GCD), and impedance spectroscopy in comparison to pure Mn3O4. Mn3O4 nanoarchitectures (15 nm) and their interaction with graphene, indicating the well-dispersion of Mn3O4 in graphene, were confirmed via TEM-SAED. The M3G1 composite, which contains mostly Mn3O4 and Mn2O3 moieties, has the largest specific capacitance of 490 F g-1 at current density of 0.25 A g-1, the highest power density of 2412 W kg−1, a considerable energy density of 45 Wh kg−1, and exceptional cycling stability of 0% loss after 1000 cycles. The quick charge diffusion mechanism, high surface area, and pore volume were all influencing factors.