The strengthening by coherent, nano-sized particles of metastable phases (pre-precipitates) continues to be the main design principle for new high-performance aluminium alloys. To describe the formation of such pre-precipitates in Al–Cu, Al–Mg, Al–Zn, and Al–Si alloys, we carry out cluster expansions of ab initio calculated energies for supercell models of the dilute binary Al-rich solid solutions. Effective cluster interactions, including many-body terms and strain-induced contributions due to the lattice relaxations around solute atoms, are thus systematically derived. Monte Carlo and statistical kinetic theory simulations, parameterized with the obtained effective cluster interactions, are then performed to study the early stages of decomposition in the binary Al-based solid solutions. We show that this systematic approach to multi-scale modelling is capable of incorporating the essential physical contributions (usually referred to as atomic size and electronic structure factors) to the free energy, and is therefore able to correctly describe the ordering temperatures, atomic structures, and morphologies of pre-precipitates in the four studied alloy systems.