Structural evolution of composite aluminium alloys with nanosize particles of metastable icosahedral quasi-crystalline phase (i-phase) under influence of pressure and temperature in the condition of warm deformation by extrusion is studied. Feedstock quasi-crystalline powder of Al-based alloy with nominal composition of Al$_{94}$Fe$_{3}$Cr$_{3}$ is chosen for experimentations and fabricates by water-atomisation technique using inhibited high-pressure water with pH = 3.5. Consolidation of powdered Al-based alloy is performed by hot extrusion process at the temperature of 380°C. Structural characterisation of as-extruded rod is performed by X-ray diffraction (XRD) analysis using CuK$_{\alpha}$-radiation, scanning and transmission electron microscopies. Differential scanning calorimetry (DSC) is employed to investigate structural stability of as-extruded rod at elevated temperatures. Mechanical characteristics (Young’s modulus, $E$, hardness number, $HV$, and yield stress, $\sigma_{0.2}$) of as-extruded rod are tested and determined by employing the novel test method procedures of indentation technique. The combined effect of elevated temperature and excessive pressure used in hot extrusion process is thought to be the cause for partial decomposition of metastable nanoquasi-crystalline particles. The crucial role of plastic deformation in terms of its influence on the thermostability of structure and mechanical properties of final products is revealed. By means of phase XRD analysis and DSC, the accelerating influence of pressure on kinetics of dissolution of i-phase particles is found, which is accompanied with decomposition of $\alpha$-Al solid solution and simultaneous formation of crystalline intermetallic phases. The uncovered features of the effect of pressure on the phase and structural transformations are connected with the acceleration of diffusion processes under formation of stable cellular structure. Taking into account the features of phase and structural transformations, the thermostability of mechanical properties of as-extruded alloy is studied. Strain hardening of Al$_{94}$Fe$_{3}$Cr$_{3}$ alloy during extrusion results in high microhardness numbers, $HV$, which exceeds by 78% those for powders of corresponding alloy. Strength properties including hardness number, $HV$, and yield stress, $\sigma_{0.2}$, of as-extruded alloy do not change their values up to 783K under annealing for 30min. Despite of strain hardening, as-extruded alloy keeps plasticity characteristic, $\delta_{H}$, just about critical value of $\cong$ 0.9 indicated in literature as criterion for ductile behaviour of metals and alloys in conventional tests by tensile and bending.