NiTi-based composites possess great potential for concurrently improving both mechanical and functional properties. However, relying on traditional alloy design principles limits the design space and greatly hinders the advancement of high-performance NiTi-based composites. The concept of high-entropy alloys has expanded the compositional landscape, unveiling unique structural characteristics for alloy design and providing new prospects for addressing these limitations. Here, we report a compositionally complex NiTi-based composite that exhibits exceptional strength and ductility, along with remarkable recoverable strain. The composite, Ni ₄₀Ti ₄₀(NbMoTaW) ₂₀ (at.%), comprises a 78.0 % B2 NiTi matrix, a 19.2 % Nb-Mo-Ta-W-Ti-Ni compositionally complex body-centered cubic (BCC) phase, and a small amount of Ti ₂Ni. Notably, this composite demonstrates an engineering compressive strength of 3274 MPa, with a compressive fracture strain of 44.2 % and a maximum recoverable strain of 7.3 % (5.6 % elastic strain and 1.7 % inelastic recoverable strain). These outstanding mechanical properties result from the unique structural characteristics of the compositionally complex phase and the lattice strain matching induced by phase transitions. The substantial recoverable strain was obtained through the reversible B2⇌R⇌B19′ phase transition. This work not only innovates a new category of high-performance NiTi-based composites but also extends the applicability of the high-entropy concept.