A high entropy alloy based self-lubricating composite with good mechanical and tribological properties was developed, using AlCoCrFeNi as matrix and MoS2 as lubricant. In addition to the well dispersed MoS2 particles, the novel composite reveals the presence of unique phases, including those rich in (Cr,Fe,Co), (Cr,Fe), (Al,Ni), Cr (σ-phase), and (Cr,S)-enriched phases. It shows excellent anti-friction and anti-wear capacities from RT to 900 °C. Friction coefficients of the composite are less than all those previously reported AlCoCrFeNi and AlCoCrFeNi-based composites under dry air wear conditions. This improvement can be correlated to the exceptional lubricating properties of MoS2, and the unique phase developed within the composite. Its excellent tribological performance is owing to MoS2 and fine wear debris at low and medium temperatures, while continuous and hard glaze layers at high temperatures. Main wear mechanisms changed from abrasion and plastic deformation to oxidation and adhesion when temperature is increased, which is attributed to the formation of a thick oxide layer on the surfaces of both counter-faces.