The present invention provides high strength, heat resistant aluminum-based alloys having a composition represented by the general formula Al.sub.a M.sub.b Ce.sub.c, wherein M is at least one metal element selected from the group consisting of V, Cr, Mn, Fe, Co, Ni, Cu and Nb; and a, b and c are atomic percentages falling within the following ranges:50.ltoreq.a.ltoreq.93, 0.5.ltoreq.b.ltoreq.35 and 0.5.ltoreq.c.ltoreq.25,the aluminum alloy containing at least 50% by volume of amorphous phase. The aluminum-based alloys are especially useful as high strength, high heat resistant materials in various applications and since they exhibit superplasticity in the vicinity of their crystallization temperature, they can be easily processed into various bulk materials by extrusion, press woring or hot-forging at the temperatures within the range of the crystallization temperature .+-.100.degree. C.