Amorphous powders of the Al-Ni-Mm system and nanocrystalline powders of the Al-Ni-Mm-Zr system (Mm ≡ misch metal) were produced by a high-pressure gas atomization technique. Following degassing, the powders were extruded with a reduction ratio of 10:1. Tensile tests were performed for as-extruded alloys. High values of tensile strength and elastic modulus were obtained in both alloy systems. The maximum tensile strength reached was as high as 1000 MPa for an Al-14·9Ni-3·3Mm–5·1Zr alloy (where the composition is in weight per cent). The structure of the Al-Ni-Mm-Zr alloys is a finely mixed structure consisting of fine intermetallic compounds of Al3Ni, Al11Mm3and Al3Zr homogeneously embedded in an ultra-fine-grained aluminium matrix. The structure of the Al-Ni-Mm-Zr alloys is finer than that of Al-Ni-Mm alloys because of the additional effect of zirconium. A Hall-Petch relationship was investigated for the Al-Ni-Mm and Al-Ni-Mm-Zr alloys. Both the grain size refinement of the aluminium matrix and the dispersion strengthening of intermetallic compounds are interpreted as contributing to the achievement of the ultra-high tensile strength.