The microstructure and mechanical properties of a (L12+B2) AlCoCrFeNi2.1 eutectic high entropy alloy (EHEA) processed by severe warm-rolling were investigated in the present work. The EHEA was successfully warm-rolled up to 90% reduction in thickness at 400 °C, 600 °C and 750 °C. Considerable differences in the microstructural evolution were identified during warm-rolling at the three temperatures. The L12 phase in the EHEA was disordered due to severe warm-rolling at 400 °C and 750 °C, while a predominantly ordered structure was retained in the EHEA warm-rolled at 600 °C. This anomalous behavior could be adequately explained by the sluggish ordering kinetics at lower deformation temperatures. The EHEA warm-rolled at 750 °C showed an extremely heterogeneous microstructure featured by retained lamellar regions comprising of B2 and FCC lamellae with dispersed B2 phase inside the FCC, whereas the non-lamellar regions showed a mixture of ultrafine to nanocrystalline disordered FCC, ordered B2 and Cr-rich σ phases. The non-lamellar regions were scarce and nearly absent in the EHEA 90% warm-rolled at 600 °C and 400 °C, respectively. The remarkably heterogeneous microstructure of EHEA warm-rolled at 750 °C resulted in outstanding strength-ductility combination with tensile strength ~1635 MPa and elongation to failure ~18%. The results indicated tremendous potential for achieving superior mechanical properties in heterogeneous EHEAs processed by severe warm-rolling. © 2019 Elsevier B.V.