A lamellar (L12 + B2) AlCoCrFeNi2.1 eutectic high entropy alloy (EHEA) was severely deformed by a novel hybrid-rolling process. During hybrid-rolling, the deformation was carried out in two stages, namely cryo-rolling followed by warm-rolling at 600 °C. The strain (ε) imparted in each of these steps was identical ~1.2, resulting in a total strain of ε~2.4 (corresponding to 90% reduction in thickness). The novel processing strategy resulted in an extremely heterogeneous microstructure consisting of retained lamellar and transformed nanocrystalline regions. Each of these regions consisted of different phases having different crystal structures and chemical compositions. The novel structure-composition dual heterogeneous microstructure originated from the stored energy of the cryo-rolling which accelerated transformations during subsequent low temperature warm-rolling. The dual heterogeneous microstructure yielded an unprecedented combination of strength (~2000 MPa) and ductility (~8%). The present study for the first time demonstrated that dual structure-composition heterogeneities can be a novel microstructural design strategy for achieving outstanding strength-ductility combination in multiphase high entropy alloys. © 2019, The Author(s).