FeCoCrNiAl high entropy alloy (HEA) matrix composite containing graphite nanoplates has been produced by spark plasma sintering (SPS). The tribological properties of this composite were tribo-tested under various loads and velocities. The results suggested that compared to the HEA, the graphite nanoplates can reduce the coefficient of friction significantly from 0.5 to 0.8 to 0.27–0.16. Under low load and velocity conditions, the reduction of friction reached 80%, and a negligible wear was obtained. Surface and interface analysis indicated that the excellent tribological performance was attributed to the in-situ formed graphene that smeared on the rubbing interface and the tribo-induced oxide layer which contained nanoscale-wear debris and graphene. The oxide scale formation and the evolution of graphene from graphite nanoplate were assessed in detail, the graphene formation process is similar to a ball milling process, and the nanoscale-wear debris formed a ball configuration that exfoliates graphite nanoplates. This work proposed a graphene formation process through the sliding induced milling, especially for the materials containing fine crystals, which contributes to the lubrication.