In the present work, various heat treatment cycles are imposed on an A356 aluminum alloy to develop two different base microstructures, one with supersaturated aluminum matrix and the other with coarse and uniformly distributed precipitates. Both the developed materials are subjected to cryorolling and then isochronally annealed for 1 hour at various temperatures ranging from 373 K to 673 K (100 °C to 400 °C). The overall strength is maximum for the cryorolled material with supersaturated base microstructure due to the dominant dislocation strengthening and precipitation strengthening mechanisms. However, the cryorolled material with precipitated base microstructure is found to have superior microstructural stability with retained ultrafine-grained (UFG) microstructure up to the annealing temperature of 473 K (200 °C) due to effective grain boundary pinning by the precipitates. Also, the material retains about 85 pct of as-cryorolled strength with enhanced ductility even after annealing at 473 K (200 °C). A detailed investigation on the microstructural evolution of the material at various annealing temperatures along with their mechanical behavior is presented in this article. © 2017, The Minerals, Metals & Materials Society and ASM International.