Recently the method for obtaining ultra-fine grained metallic materials has developed using severe plastic deformation (SPD), such as equal channel angular pressing (ECAP), accumulative roll bonding (ARB), torsion straining, and warm multiple deformation (WMD) etc. In order to enhance thermal stability of ultra-fine grained aluminum alloys manufactured by SPD process, the addition of Sc and Zr elements has been considered to devise fine Al3Sc, Al3Zr and Al3(Scx Zr1-x) precipitates for inhibiting the grain growth. In this study, the microstructure evolution has been investigated in Al-Mg alloys with and without Sc and Zr addition during the warm multiple deformation process. In addition Al-Mg alloys were compressed at a strain rate of 10-1 sec-1 by two different routes, that is, route A and route B. Route A is to rotate the specimen throughout 90o around the vertical axis of loading direction at every pass. Route B is to rotate the specimen throughout 90o around the parallel axis of loading direction and then rotate it again as route A. The specimen deformed by route B had finer grain size and more uniform distribution of grains than those deformed by route A. When the warm multiple deformation process repeated up to 8 passes at 673 K, the specimen consisted of ultra-fine grained structure with the average grain size less than 3 μm. The superplastic behavior can also be observed at the high strain rate and low temperature regime.