• Giant strengthening in Al 0.1 CrFeCoNi by cold rolling and short-time annealing. • Al 0.1 CrFeCoNi possesses yield strength of 885 MPa and uniform elongation of 23.4%. • Ultrafine-grained structure and multiple deformation twins lead to high strength. Grain refinement usually makes the materials stronger, while ductility has a dramatic loss. Here, a superior tensile strength–ductility synergy in a fully recrystallized ultrafine-grained (UFG) Al 0.1 CrFeCoNi with abundant annealing twins was achieved by cold rolling at room temperature and short-time annealing. The microstructure characterization using electron backscattered scattering diffraction demonstrates that abundant geometrically necessary dislocations (GNDs) gather around the grain boundaries and twin boundaries after tensile deformation. Although coarse-grained (CG) samples undergo a larger plastic deformation than UFG samples, the GND density decreases with grain size ranging from UFG to CG. Transmission electron microscopy results reveal that the annealing twin boundary, which effectively hinders the dislocation slip and stores dislocation in grain interior, and the activation of multiple deformation twins are responsible for the superior strength–ductility synergy and work hardening ability. In addition, the yield strength of fully recrystallized Al 0.1 CrFeCoNi follows a Hall–Petch relationship ( σ y = 24 + 676 d –1/2 ), where d takes into account both grain boundaries and annealing twin boundaries. The strengthening effects of grain boundaries and annealing twin boundaries were also evaluated separately.