The recrystallization behavior of an Al-Cu-Mg alloy is investigated in multi-directionally forged over-aged and solution treated alloys, during non-isothermal annealing. Deformation and non-isothermal annealing are performed with a Gleeble 3800 thermo-mechanical simulator. The hardness measurements show that there is a thermal stability in mechanical properties during non-isothermal annealing up to 250 °C with heating rate of 10 K·min− 1. Differential scanning calorimetry curves of deformed over-aged and solution treated alloys describe the related precipitation phenomena. EBSD maps demonstrate that partially recrystallized and fully recrystallized microstructures appear in deformed over-aged and solution treated alloys, respectively. During over ageing, small S′/S particles are formed and increase the critical particle diameter for particle stimulated nucleation (PSN). Evidence is also reported on grain boundary bulging in the over-aged alloy, related to strain induced grain boundary migration (SIBM). In the solution treated case, since there is not sufficient time for S′/S phase growth during non-isothermal annealing, Zener pinning pressure is reduced and PSN sites can be activated. The association of recrystallized microstructure and randomly oriented grains confirms that PSN is the governing nucleation mechanism in deformed solution treated alloys. In the deformed over-aged alloy, a strong γ-fiber is developed by consuming other texture components like {001}〈110〉