Ultra-fine grained (UFG) materials can be produced by several techniques involving severe plastic deformation (SPD). Accumulative Roll Bonding (ARB) is one of the SPD methods that enable the production of large amounts of UFG sheets. UFG sheets were prepared by up to six cycles of ARB at ambient temperature from an Al-0.22Sc-0.13Zr alloy in two states: a non-agehardened and a peak-aged. The effect of Al3(Sc1-xZrx) precipitates on the thermal stability of the UFG structures produced by ARB was investigated by isochronal annealing at temperatures between 200 and 550 °C. Additionally, the non-age-hardened ARB material was peak-aged prior to annealing and annealed together with both as-ARB-processed materials. The changes of microstructure and hardness due to annealing were studied. Annealing at 300 °C induces an additional strengthening in both non-pre-aged ARB materials that may be ascribed to precipitation and growth of coherent Al3(Sc1-xZrx) particles. This result suggests that the hardness decrease introduced by ARB in the peak-aged specimen is due to dissolution of precipitates during deformation. The annealing response of the materials above 300 °C does not depend on their thermal pre-treatment. However, the finely dispersed Al3(Sc1-xZrx) precipitates stabilise the refined deformed microstructure suitable for superplastic forming up to relatively high temperatures.