Motivated by an increased focus on recycling of aluminium alloys, for which elements like Mn, Fe and Si tend to increase, a comprehensive investigation of the softening behavior during annealing after cold rolling of Al-Mn-Fe-Si alloys has been carried out. It is clearly demonstrated that the kinetics and final microstructure are the result of a delicate balance between processing conditions and microchemistry. In general, at the same processing condition, more and finer dispersoids, whether pre-existing or formed during annealing (concurrent precipitation) strongly affect the kinetics and either mainly suppress recrystallization or give coarse non-equiaxed recrystallized grains. Faster softening kinetics is observed at large deformations and conditions less affected by dispersoids, together with equiaxed fine grains. The precipitation behavior before the completion of recrystallization is accelerated by high solid solution levels of Mn, large deformations and high temperature. However, even with a strong supersaturation of Mn in solid solution, annealing at high temperature accelerates recrystallization so that it is mainly completed before substantial concurrent precipitation take place, giving a fine equiaxed grain structure. Moreover, annealing treatments at low heating rates produce more inhomogeneous microstructures than isothermal annealing.