Using different homogenization treatments, different initial microchemistry conditions in terms of solid solution levels of Mn, and number densities and sizes of constituents and dispersoids were achieved in an Al-Mn-Fe-Si model alloy. For each homogenized condition, the microchemistry and microstructure, which further change both during deformation and subsequent annealing, were quantitatively characterized. The influence of the different microchemistries, with special focus on different particle structures (constituents and dispersoids), on the softening behavior during annealing after cold rolling and the final grain structure has been systematically studied. Time-Temperature-Transformation diagrams with respect to precipitation and recrystallization as a basis for analysis of the degree of concurrent precipitation during back-annealing have been established. Densely distributed fine pre-existing dispersoids and/or conditions of significant concurrent precipitation strongly slows down recrystallization kinetics and lead to a grain structure of coarse and strongly elongated grains. At the lowest annealing temperatures, recrystallization may even be completely suppressed. In conditions of low number density and coarse pre-existing dispersoids, and limited additional concurrent precipitation, recrystallization generally results in an even, fine and equi-axed grain structure. Rough calculations of recrystallized grain size, assuming particle stimulated nucleation as the main nucleation mechanism, compare well with experimentally measured grain sizes.