Eutectic high-entropy alloys (EHEAs) represent attractive candidate materials for overcoming the strength-ductility trade-off, which can be enhanced through the directional alignment of the lamellar structure along the loading direction. Here, we put forward a new route to optimize the strength-ductility synergy without orientation dependence. Through a combination of severe plastic deformation and annealing, we convert the initially lamellar structure into a dual-phase structure comprised of ultrafine equiaxed grains. The significant grain refinement improves the yield strength from 703 MPa to 1199 MPa without sacrificing any ductility. During deformation, the localized softening resistance of the achieved dual-phase microstructure avoids necking, and the intrinsic microcrack-arresting mechanism effectively improves the fracture resistance. Grain boundaries and phase boundaries provide nucleation sites for dislocations and restrict dislocation transfer while the strain incompatibility is accommodated by geometrically necessary dislocations. This work demonstrates that dual-phase alloys comprised of ultrafine equiaxed grains provide a pathway for strengthening without loss of ductility.