New Al-based alloys with very high ultimate tensile strength were developed in high Al concentration range of 91-95 at.% for Al-Fe-Cr-Ti-M (M: Co and Mo) systems and Al-Fe-Cr-Mo-Ti-Co system by the dispersion of nanoscale quasicrystalline particles in Al phase. The effect of adding elements, M was discussed in the viewpoint of stability of super-cooled liquid state and formation ability of quasicrystalline phase. The P/M Al-Fe-Cr-Ti-M alloys with dispersed nanoscale quasicrystalline particles exhibited ultimate tensile strength of 350MPa at 573K and 200MPa at 673K.