Bulk ultrafine-grained (UFG) AA6063/4wt pct SiC composites with varying reinforcement sizes [12 µm (coarse), 1 µm (fine), and 45 nm (nano)] have been developed by a hybrid route of stir-casting and cryorolling. In the current study, the influence of annealing temperatures (423 K to 573 K) on the precipitation evolution, particle-stimulated nucleation (PSN), recrystallization, grain growth kinetics, and thermal stability of developed bulk UFG composites have been studied, and the resultant effect of microstructural evolution is correlated with mechanical properties. UFG coarse and UFG fine composites have shown evidence of recrystallized grains via PSN and retained their UFG microstructure up to 473 K and 523 K, respectively. Superior microstructural stability with retained UFG microstructure up to 573 K was observed in the UFG nanocomposite due to the effective pinning of nano-SiC particles and precipitates along grain boundaries. This ultimately resulted in the increased grain growth activation energy and strength of the UFG nanocomposite. However, the overall increase in strength is maximum in the UFG nanocomposite due to the dominant effect of dislocation strengthening, grain boundary strengthening, and precipitation strengthening mechanisms. A thorough examination of the microstructural evolution of UFG composites at different annealing temperatures along with their mechanical behavior is presented in this paper. © 2019, The Minerals, Metals & Materials Society and ASM International.