Alloying additions of Sc and Zr raise the yield strength of Al-Mg alloys significantly. We have studied the effects of Sc and Zr on the grain refinement and recrystallization resistance of Al-Mg alloys with the aid of computational alloy thermodynamics. The grain refinement potential has been assessed by Scheil–Gulliver simulations of solidification paths, while the recrystallization resistance (Zener drag) has been assessed by calculation of the precipitation driving forces of the Al3Sc and Al3Zr intermetallics. Microstructural performance indices have been derived, used to rank several alloy composition variants, and finally select the variant with the best combination of grain refinement and recrystallization resistance. The method can be used, with certain limitations, for a thermodynamics-based design of Al-Mg and other alloy compositions.