Thermal stability, kinetics and decomposition mechanisms of the nanophase composites (Al nanocrystals + residual amorphous matrix) formed at the first crystallization stage of amorphous Al$_{90}$Y$_{10}$, Al$_{87}$Ni$_{8}$Gd$_{5}$, and Al$_{86}$Ni$_{6}$Co$_{2}$Gd$_{6}$ alloys are investigated by X-ray diffractometry, transmission electron microscopy, differential scanning calorimetry, and measurements by both electrical-resistance and microhardness techniques. The second crystallization stage is final for the first two amorphous alloys, while the Al$_{86}$Ni$_{6}$Co$_{2}$Gd$_{6}$ alloy transforms into wholly crystalline state at the third crystallization stage. As shown, the highest values of microhardness (3.8—5.4 GPa) are reached in amorphous—nanocrystalline structural states, and the level of softening, which is caused by complete crystallization of a residual amorphous phase, essentially increases with enlargement of the average grain size of the structural components. By the analysis of the second crystallization stages kinetics, performed within the classical Kolmogorov—Johnson—Mehl—Avrami model, together with the results of structural investigation, it is found that the second crystallization stages in the investigated amorphous alloys occur via three different mechanisms, i.e., by homogeneous nucleation and diffusion-controlled growth of nanocrystals of the metastable intermetallic Al$_{4}$Y compound simultaneously with pre-existing Al nanocrystals (in Al$_{90}$Y$_{10}$), by transient nucleation with increasing rate and the interface-controlled growth of equilibrium Al$_{3}$Ni and Al$_{23}$Ni$_{6}$Gd$_{4}$ intermetallics (in Al$_{87}$Ni$_{8}$Gd$_{5}$), and by the diffusion-limited growth initiated by formation of nanoscale particles of non-identified metastable intermetallic compound (in Al$_{86}$Ni$_{6}$Co$_{2}$Gd$_{6}$). As shown, the values of the temperature ranges of the two-phase nanocomposite structures’ stability and the activation energies of their decomposition correlate with each other, and both of them are appreciably higher for the alloys, where the second crystallization stages are final and take place by means of mechanisms of nucleation and growth of metastable or equilibrium intermetallic crystals.