Strength-ductility synergy of the Al0.1CrFeCoNi high-entropy alloy can be tuned largely by cold-rolling followed by annealing treatments. However, strain-hardening behaviors and the underlying deformation mechanisms of the low-to high-temperatures-annealed microstructures have not been well clarified. In this paper, the Al0.1CrFeCoNi high-entropy alloy was cold-rolled, followed by annealing at 673-1273 K to investigate the effect of annealing temperatures on the microstructure and deformation behavior. Annealing at 673, 873, 1,073, and 1273 K resulted in no recrystallization, partial recrystallization, full recrystallization, and grain-coarsening, which yielded a stretched-grained, heterostructured, fine-recrystallized, and coarse-grained microstructure, respectively. The heterostructured microstructure was comprised of stretched, partially recrystallized, and fine recrystallized grains. Uniaxial tension results show that the 873 K-annealed specimens possessed a good combination of strength (a yield strength of similar to 746 MPa) and ductility (a uniform elongation of similar to 28%), compared with the high-strength-yet-low-ductility cold-rolled and 673 K-annealed specimens, and the high-ductility-yet-low-strength 1073 and 1273 K-annealed specimens. The relationship between the yield strength and average grain sizes of the Al0.1CrFeCoNi high-entropy alloy follows the Hall-Petch equation with a friction stress of similar to 137 MPa, and a high Hall-Petch coefficient of similar to 664 MPa.mu m1/2. Five and three different regimes existed in the strain-hardening rate versus true strain curves for the 873, and 1073 and 1273 K-annealed samples, respectively. The occurrence of the second and fourth regimes, and the second regime were detected essentially caused by nanotwinning. The correlation between microstructure, tension properties, deformation mechanism, and strain-hardening behavior is discussed.