Graphene decorated with well-dispersed cubic fluorite ceria (CeO₂) nanoparticles was prepared through a simple hydrothermal method. The as-prepared CeO₂/graphene composites (COGNCs) were further used as lubricant additives in the base oil of liquid paraffin to investigate their tribological properties by the Optimol SRV-1 oscillating reciprocating friction and wear tests in air (relative humidity, 17%). The results indicated that the introduction of a small amount of COGNCs into the base oil could reduce friction and wear drastically under a high load condition, which was better than the testing results of graphene or CeO₂ nanoparticles. Specifically, when 0.06 wt% COGNCs was added into the base oil, the average friction coefficient could be reduced from 0.21 to 0.10, and the wear rate could be decreased to 1.5% of that of base oil. The excellent tribological properties of COGNCs can be explained by the synergistic friction reduction and antiwear effects of graphene and CeO₂ nanoparticles.