Nano-lamellar (L12 + B2) AlCoCrFeNi2.1 eutectic high entropy alloy (EHEA) was processed by cryo-rolling and annealing. The EHEA developed a novel hierarchical microstructure featured by fine lamellar regions consisting of FCC lamellae filled with ultrafine FCC grains (average size ∼200-250 nm) and B2 lamellae, and coarse non-lamellar regions consisting of ultrafine FCC (average size ∼200-250 nm), few coarse recrystallized FCC grains and rather coarse unrecrystallized B2 phase (∼2.5 μm). This complex and hierarchical microstructure originated from differences in strain-partitioning amongst the constituent phases, affecting the driving force for recrystallization. The hierarchical microstructure of the cryo-rolled and annealed material resulted in simultaneous enhancement in strength (Yield Strength/YS: 1437 ± 26 MPa, Ultimate Tensile Strength/UTS: 1562 ± 33 MPa) and ductility (elongation to failure/ef ∼ 14 ± 1%) as compared to the as-cast as well as cold-rolled and annealed materials. The present study for the first time demonstrated that cryo-deformation and annealing could be a novel microstructural design strategy for overcoming strength-ductility trade off in multiphase high entropy alloys. © 2018 The Author(s).