Possibilities of enhancing mechanical properties of brittle intermetallic containing high entropy alloys (HEAs) using novel processing and microstructural design strategies were investigated in the present work. For this purpose, homogenized CoCrFeNi2.1Nb0.2 HEA consisting of FCC matrix and complex Laves phase particles was successfully processed by severe cold- or cryo-rolling to 90% reduction in thickness followed by annealing (800 °C/1 hour(h)). As compared to cold-rolling, cryo-rolling resulted in a finer lamellar nanostructure and decidedly greater fragmentation of the Laves phase. Upon annealing, the cold-rolled HEA showed a recrystallized FCC matrix dispersed with D019 structured ε nano-precipitates. In contrast, the finer nanostructure and greater driving force for accelerated precipitation of profuse nano-precipitates at the early stages of annealing inhibited recrystallization in the cryo-rolled HEA and resulted in the formation of heterogeneous microstructure consisting of retained deformed and recrystallized regions. The novel heterogeneous microstructure of the cryo-rolled and annealed HEA resulted in a remarkable enhancement in strength-ductility synergy. The present results indicated that cryo-rolling could be used as an innovative processing strategy for tailoring heterogeneous microstructure and achieving novel mechanical properties. © 2020, The Author(s).