In this work, the effects of solute Fe, Zn, and Mg on the suppression of recrystallization in Al are studied. The materials are Al-22.2 atomic parts per million (at ppm) Fe, Al-53.6 at ppm Fe, Al-0.1 at% Mg, Al-1.1 at% Mg, Al-0.1 at% Zn, and Al-3.0 at% Zn. All were synthesized using high-purity starting materials. The amount of impurities other than the additional elements is less than a few ppm. The variation in the Vickers hardness with annealing time after isothermal annealing treatments at various temperatures is measured. The results of the isothermal annealing treatments are discussed in terms of the Johnson–Mehl–Avrami–Kolmogorov (JMAK) equation. The effect of the suppression of recrystallization per concentration unit is highest for Fe, less so for Mg, and least for Zn. The values of the apparent activation energy for recrystallization are calculated as: 139, 146, 63, 66, 47.7, and 67 kJ/mol for Al-22.2 at ppm Fe, Al-53.6 at ppm Fe, Al-0.1 at% Mg, Al-1.1 at% Mg, Al-0.1 at% Zn, and Al-3.0 at% Zn, respectively. The values of the apparent activation energy for recrystallization are close to the values of the activation energy for grain boundary diffusion in the same alloy systems.