The mechanical alloying processes was employed to fabricate Al-4at.%Zr alloy with nano-sized grains and very fine Al3Zr compounds. The phase transformations and the stability of the phases formed during mechanical alloying and heat treatment processes were investigated. The grain sizes of the alloys immediately after milling and following the subsequent heat treatment at 550°C were 54.2nm and 106.4nm, respectively. Some of Zr atoms were dissolved into the Al matrix and most of them reacted with hydrogen produced by decomposition of PCA(process control agent) to form ZrH2 during mechanical alloying process. These ZrH2 hydrides decomposed gradually after the heat treatment. Stable Al3Zr with a DO23 structure was formed by heat treatment at temperature of more than 4500C. The hardness of the Al-4at.%Zr alloy was more than two times higher than those of other Al-based alloys.