Nano-quasi-crystalline Al—Fe—Cr-based alloys composed of nanosize icosahedral quasi-crystalline particles embedded in the $\alpha$-Al matrix exhibit a high strength at elevated temperatures compared to commercial Al alloys. In this point, basic knowledge concerning structural stability is important for application of Al—Fe—Cr-based alloys in engineering practice. Investigation of thermal evolution of rapid-quenched melt-spun Al-based alloy with nominal composition of Al$_{94}$Fe$_{3}$Cr$_{3}$ is the subject matter of the present study. X-ray diffraction (XRD) analysis and transmission electron microscopy (TEM) are used for microstructural characterisation of the above-mentioned alloy heat-treated at different temperatures during 30 min. In addition, microindentation technique is applied to reveal a correspondence of microstructure with strength and ductility of Al$_{94}$Fe$_{3}$Cr$_{3}$ alloy in as-spun state and after heat treatment. A number of mechanical characteristics including Young’s modulus, $E$, Vickers microhardness, $HV$, yield stress, $\sigma_{0.2}$, and plasticity characteristic, $\delta_{H}$, all determined by state-of-the-art testing method procedures, are measured to specify strength and ductility of the rapid-quenched melt-spun Al$_{94}$Fe$_{3}$Cr$_{3}$. The results showed that quasi-crystalline particles survive in the microstructure of Al$_{94}$Fe$_{3}$Cr$_{3}$ alloy heat-treated up to the temperature of 400°C. However, gradual dissolution of quasi-crystalline particles and simultaneous formation of metastable crystalline Al$_{6}$Fe particles occur at the temperature above 400°C. Heat treatment of the rapid-quenched melt-spun Al$_{94}$Fe$_{3}$Cr$_{3}$ alloy at the temperature of 550°C and higher results in transition of metastable Al$_{6}$Fe phase into stable crystalline $\theta$-phases, i.e. Al$_{13}$Cr$_{2}$ and Al$_{13}$Fe$_{4}$. Combination of high strength and quite-enough ductility is found to be true for the as-spun Al$_{94}$Fe$_{3}$Cr$_{3}$ alloy. Mechanical characteristics do not change so much when Al$_{94}$Fe$_{3}$Cr$_{3}$ alloy is heated up to the 400°C, since quasi-crystalline particles remain in the microstructure. Disappearance of quasi-crystalline particles after heat treatment of Al$_{94}$Fe$_{3}$Cr$_{3}$ alloy at the temperature higher than 400°C causes strength properties to be decreased considerably although plasticity characteristic increases up to the critical value $\delta_{H} \cong 0.9$ considered as criterion for ductile behaviour of metals and alloys in conventional tests by tensile and bending.