<p>The pursuit of advanced wear-resistant materials for cryogenic applications is often hindered by a fundamental trade-off of enhancing strength and damage tolerance. CoCrNi-based medium-entropy alloys (MEAs), while excellent in cryogenic toughness, suffer from this very limitation. Although second-phase reinforcement boosts strength, the strain incompatibility between phases inevitably triggers cracking, which is severely exacerbated at low temperatures. This work introduces a novel microstructural design strategy based on regulated partial recrystallization to overcome this longstanding challenge. By tailoring the thermomechanical processing of a (CoCrNi)₉₀Mo₁₀ MEA, we engineered a unique architecture where a fully recrystallized FCC phase is homogeneously embedded within a continuous skeleton of a hard, non-recrystallized σ phase. The alloy with this optimized microstructure achieved a remarkably low wear rate at 113 K that is less than half of its as-cast and fully recrystallized counterparts. The experimental and modeling results indicate the underlying synergy: the σ skeleton provides robust structural support and distributes stress deeply, while the recrystallized FCC phase, with its high density of grain boundaries and annealing twins, acts as a compliant strain-accommodating medium, effectively suppressing interfacial cracking. This combined “skeleton effect” and “recrystallization effect” not only delivers exceptional cryogenic wear resistance but also offers a practical strategy for designing high-performance, crack-resistant dual-phase composites for extreme environments.</p>