High-temperature heat treatments can improve the element distributions and phase structures of AlCoCrFeNi high entropy alloys (HEAs). However, the long-term isothermal annealing at high temperatures will make the grains grow crazily. In this study, the problem of grain growth caused by high-temperature annealing at 1200 °C was solved by heavily deformed AlCoCrFeNi HEAs. The ultrafine grains formed by dynamic recrystallization will grow firstly during the subsequent annealing process, which inhibits the increase in the larger grains in the hot-extruded AlCoCrFeNi HEAs. The effect of high-temperature annealing on hot-extruded AlCoCrFeNi HEAs was also explored simultaneously in detail. After annealing at 1200 ℃ for 2 h, the compressive strength and fracture strain of the AlCoCrFeNi HEA reached an astonishing result of 3750 MPa and 43%, respectively. The results are attributed to the skeleton-liked FCC structures deeply interspersed into the grains and more importantly, the fine annealed grains which still maintained an average diameter of 20 μm. Additionally, the new nano-precipitates did not expand wildly at high temperatures either. Research on heavily deformed AlCoCrFeNi HEAs isothermally annealed at 1200 °C provides an available idea for further improving the properties of these HEAs.