Realizing improved strength-ductility synergy in eutectic alloys acting as in situ composite materials remains a challenge in conventional eutectic systems, which is why eutectic high-entropy alloys (EHEAs), a newly-emerging multi-principal-element eutectic category, may offer wider in situ composite possibilities. Here, we use an AlCoCrFeNi2.1 EHEA to engineer an ultrafine-grained duplex microstructure that deliberately inherits its composite lamellar nature by tailored thermo-mechanical processing to achieve property combinations which are not accessible to previously-reported reinforcement methodologies. The as-prepared samples exhibit hierarchically-structural heterogeneity due to phase decomposition, and the improved mechanical response during deformation is attributed to both a two-hierarchical constraint effect and a self-generated microcrack-arresting mechanism. This work provides a pathway for strengthening eutectic alloys and widens the design toolbox for high-performance materials based upon EHEAs.