Second phase strengthening has been applied to high entropy alloys (HEAs) for optimizing mechanical properties. In this study, by conducting mechanical testing of a eutectic dual-phase AlCoCrFeNi HEA with homogenous distribution of body-centered cubic (BCC) and face-centered cubic (FCC) lamellar phases inside a transmission electron microscope, we found that although BCC was truly the hard phase, decreasing the proportion of BCC phase in fact increased the strength due to the existence of chemically disordered semi-coherent phase boundaries, which acted as potent impediments to dislocation motion resulting in dense dislocation storage in FCC phases. Moreover, the difficulty in dislocation glide caused massive cross-slip, and the interaction between primary slip arrays and cross-slip systems during deformation increased the rate of dislocation accumulation by forming dislocation substructures, thus making the FCC phases exceptionally strong. Our findings not only revealed the underlying strengthening mechanism of eutectic dual-phase AlCoCrFeNi HEAs, but also shed light on new ways in further optimizing the mechanical properties of HEAs.