Although grease can effectively lubricate machines, lubrication failure may occur under high speed and heavy load conditions. In this study, Mn3O4/graphene nanocomposites (Mn3O4#G) were synthetized using a hydrothermal method as lubricant additives. The lubrication properties of compound grease with Mn3O4#G nanocomposite additive under heavy contact loads of 600–900 N (3.95–4.59 GPa) were investigated. First, the nanocomposites were dispersed into L-XBCEA 0 lithium grease via successive electromagnetic stirring, ultrasound vibration, and three-roll milling. Compound grease with additives of commercial graphene (Com#G) was also investigated for comparison. Tribological test results revealed that the trace amounts of Mn3O4#G (as low as 0.02 wt％) could reduce the coefficient of friction (COF) of grease significantly. When the concentration of Mn3O4#G was 0.1 wt％, the COF and wear depth were 43.5％ and 86.1％, lower than those of pure graphene, respectively. In addition, under the effect of friction, the microstructure of graphene in Mn3O4#G nanocomposites tends to be ordered and normalized. Furthermore, most of the Mn3O4 transformed into Mn2O3 owing to the high temperature generated from friction. Using the Ar gas cluster ion beam sputtering method, the thickness of the tribofilm was estimated to be 25–34 nm. Finally, the improvement of the lubrication properties was attributed to the synergistic effect of the adsorbed tribofilm, i.e., the graphene island effect and the filling effect of Mn3O4#G.