The ultra-fine grain Al-4Zr alloy has been successfully fabricated by a mechanical alloying process. The intermetallic Al3Zr phases strongly enhance the mechanical properties of Al-based alloy and prevent grain growth of alloy. The phase stability and transformation during mechanical alloying process have been investigated. The ultra-fine grain alloy has been successfully obtained. The thin film of Al-4Zr alloy has been observed by a transmission electron microscope. The equivalent grain size of as-milling specimen is 55 nm. After milling process, the specimens were heat treated at 350 °C to 650 °C. The equivalent grain size of heat treated specimens were 80 nm at 350 °C and 130 nm at 650 °C. Some of Zr atoms were dissolved into the Al matrix and most of them reacted with hydrogen produced by decomposition of PCA to form ZrH2 during mechanical alloying process. These ZrH2 hydrides decomposed gradually after the heat treatment. Stable A13Zr with a D023 structure was formed by heat treatment at temperature of 550 °C.