A CoCrFeNi high entropy alloy matrix self-lubricating composite was prepared by spark plasma sintering using a mixture of CoCrFeNi high entropy alloy powder, nickel-coated graphite powder and nickel-coated MoS₂ powder. The composite consisted of four phases: face-centered cubic phase of the high entropy alloy, graphite, MoS₂ and nickel. Graphite and MoS₂ existed in the composite were mainly due to the nickel coatings onto the lubricants and the unique advantage of spark plasma sintering. The hardness, yield strength, compressive strength and fracture toughness of the composite were 271 HV, 610 MPa, 921 MPa and 14.3 MPa·m^0.5, respectively. The good mechanical properties of the composite were mainly derived from the CoCrFeNi high entropy alloy matrix. The composite exhibited excellent tribological properties from room temperature to 800 °C. From room temperature to medium temperatures, the reduction of friction coefficients and wear rates of the composite was attributed to the synergistic lubricating effect of graphite and MoS₂. At high temperatures, it was found that various metal oxides formed on the composite surfaces played a key role in improving the tribological properties.