By the dispersion of nanoscale quasicrystalline and amorphous particles in Al phase, new Al-based alloys with good mechanical properties were developed in a high Al concentration range of 93–95 at.% for Al−Cr−Ce−Co, Al−V−Fe, Al−Ti−M and Al−Fe−Cr−Ti alloy systems. The Vickers hardness of a melt-quenched (MQ) Al84.6Cr15.4 alloy with almost a single icosahedral quasicrystalline phase (QC) was 710. The addition of Ce and Co in the Al−Cr binary alloys was effective for the extension of the concentration range of the QC to a lower solute concentration range. The fracture strength (σf) increased to 1340 MPa for the MQ Al94.5Cr3Ce1Co1.5 alloy in which the particle size and volume fraction were approximately 40 nm and 70%, respectively. The σf of the MQ Al94V4Fe2 alloy was 1390 MPa and the particle size and volume fraction were about 10 nm and 50%, respectively. Similarly, σf of the MQ Al93Ti4Fe3 alloy was 1320 MPa and the particle size and volume fraction were about 11 nm and 30%, respectively. Power metallurgy (P/M) Al93Fe3Cr2Fe2 alloy with dispersed nanoscale QC exhibited ultimate tensile strength (σUTS) of 660 MPa, 0.2 % proof stress (σ0.2) of 550 MPa, plastic elongation (εP) of 4.5%, Young's modulus (E) of 85 GPa, Vickers hardness (Hv) of 192 and specific strength (σUTS/ρ) of 2.20×105 Nm/kg at room temperature and σUTS of 350 MPa, σ0.2 of 330 MPa and εP of 1.5% at 573 K. The QC structure in the P/M Al93Fe3Cr2Ti2 alloy remained almost unchanged even after annealing for 720 ks at 573 K and good wear resistance against S50C steel was also maintained for the extruded alloy tested at sliding velocity of 0.5 to 2 m/sec. These mechanical properties are promising for the future extension of the new Al-based alloys to practical materials.