The effect of pre-existing nano sized precipitates on the mechanisms and rate of grain refinement has been investigated during the severe plastic deformation. A binary Al–0.2Sc alloy, containing coherent Al₃Sc particles, of 3.62 nm in diameter has been deformed by accumulative roll bonding up to 10 cycles. The resulting deformed structures were quantitatively analyzed using electron backscattered diffraction and transmission electron microscope techniques, and the results have been compared to those obtained from a solution treated Al–0.2Sc alloy, deformed up to same accumulative roll bonding cycles. The fraction of high-angle grain boundaries and grain size in all materials was increased and decreased gradually with increasing equivalent strain, respectively. However, the Aged-ARB alloy had relatively higher fraction of high-angle grain boundaries and smaller grain size than those of ST-ARB specimens at the same accumulative roll bonding cycles. It was found in an Al-0.2%Sc alloy that starting microstructures significantly affect the formation of ultrafine grains during severe plastic deformation. It was shown that the small Al₃Sc precipitates are more effective on microstructural evolution during accumulative roll bonding process. Existence of fine precipitates in the starting material greatly accelerated the microstructure refinement. In this regards some unique phenomena, including softening during severe plastic deformation and dissolution of pre-existing Al₃Sc, were observed.