Metal matrix composites containing graphene show excellent lubricating performance, while the detailed atomic scale understanding about the origin of this superior lubrication is still absent. In this study, the self-lubricating behaviors of Cu-based nanocomposites embedded with graphene nanoflakes (GNFs) were investigated by large-scale molecular dynamics simulations. The simulation results indicate that the friction reduction was achieved via the reorientation of GNFs in polycrystalline Cu matrix. We found that the friction coefficient is closely related to the coverage ratio of GNFs at the sliding interface, as the formation of van der Waals gaps in GNFs and between GNF and Cu matrix will reduce the sliding resistance. Especially, a minimum friction coefficient could be obtained when GNFs spread over the whole sliding interface. In addition, the number of layers, flake size and initial orientation angle of GNFs together with multiple GNFs in Cu matrix have also been considered. The simulated results indeed confirm the formation of van der Waals gap behaves as an effective mechanism to reduce the sliding friction.