The mechanical properties of the AlCoCrFeNi high-entropy alloy (HEA) can be significantly enhanced by grain refinement. However, it is difficult to refine the grain size of AlCoCrFeNi HEA by solidification methods. In this study, fine-grained AlCoCrFeNi HEA was successfully prepared by heavy thermal mechanical processing. The AlCoCrFeNi HEA consists of FCC, B2, and BCC phases. The FCC phase is distributed on grain boundaries, while the B2 phase is embedded in the BCC matrix within the grains. The fine-grained AlCoCrFeNi HEA has enhanced strength and ductility compared with its coarse-grained counterpart. The enhanced strength–ductility synergy of the fine-grained AlCoCrFeNi HEA is attributed to three key factors: the fine-grained microstructure, the delayed initiation of cracks within the hard-to-deform grain matrix, and the impediment of crack propagation by the grain boundaries enriched with the FCC phase.