Severe plastic straining is an established method for producing submicron grain (SMG) structures in alloys. However, the development of such a fine grained structure in single-phase alloys is usually futile if they are to be exposed or processed at elevated temperatures. This is a direct consequence of the natural tendency for rapid and substantial grain coarsening which completely removes the benefits obtained by grain refinement. This problem may be avoided by the introduction of nanosized, highly stable particles in the metal matrix. In this work, a SMG structure was generated in an Al-0.3 wt.% Sc alloy by Equal Channel Angular Pressing (ECAP). The alloy was prepared initially to produce a fine grained microstructure exhibiting a large fraction of high angle grain boundaries and a dispersion of nanosized Al3Sc particles. The evolution of microstructure during annealing at temperatures up to 550 °C was examined in detail and grain size distributions generated from the data. It was shown that grain coarsening is rapid at temperatures above 450 °C and the initial log-normal grain size distribution exhibiting low variance and skewness was altered considerably. The statistical information generated from the grain size distributions confirms that discontinuous grain coarsening occurs in this alloy only at temperatures greater than 500 °C.