The aluminum-zirconium (Al-Zr) alloys are of interest because of their superior thermal stability and good electrical conuctivity, but their main drawback is their rather low hardness (<75 Hv) even after severe plastic deformation (SPD). These alloys, which are actually composites of Al and Al₃Zr intermetallics (D0₂₃ tetragonal structure), do not show age-hardening behavior due to the immiscibility of Zr in Al. In this study, ultra-SPD with shear strains up to 40,000, realized by high-pressure torsion (HPT), is employed to generate supersaturated solid solution in an Al-Zr alloy. Subsequent aging leads to unusual precipitation of AlZr precipitates at grain boundaries (Bf orthorhombic structure) and of coherent metastable Al₃Zr precipitates within grain interiors (L1₂ cubic structure). It is found that the supersaturation of Zr in Al by ultra-SPD is controlled by an ultrafast dynamic diffusion which is comparable to surface diffusion, while the formation of precipitates by static aging is controlled by lattice and pipe diffusions. These microstructural features provide exceptional increase in hardness up to 148 Hv, great thermal stability up to 523 K and reasonable electrical conductivity up to 35 %IACS. Detailed analysis shows that ~30% of this hardening is caused by precipitation strengthening, while extra hardening is achieved due to nanograin formation, grain-boundary segregation and dislocation accumulation. This study introduces a rational approach to produce novel age-hardenable Al alloys with high thermal stability and reasonable electrical conductivity by application of ultra-SPD.