CoCrNi medium-entropy alloys (MEAs) system has been hailed as the potential high strength and ductile structural materials. However, the study on their tribological behaviors over a wide temperature range is still scarce. The current work investigates the effects of heterogeneous (Al, Ti) on the phase evolution, mechanical and high-temperature tribological performances of the MEAs. (Al, Ti) endows the MEAs a considerable solutal effect, which triggers the transformation from FCC-dominated single-phase structure to dual heterostructure containing FCC matrix and yarn-like structures/coupled BCC phases. Our designed MEA has an ultrahigh compressive yield strength of 2.0 GPa and a plasticity of 12.3%. Tribological properties of the designed MEA are temperature dependent. (Al, Ti) enhances the wear-resistance of MEA by five times due to the mitigation of abrasive wear below 400°C. While between 400°C and 600°C, (Al, Ti) intensifies the adhesive wear instead, leading to severe wear. When it reaches 800°C, (Al, Ti) will induce the tribo-chemistry to form the lubricative glaze-layer that minimises wear.