The effect of partial and full substitution of Ni by Co in the amorphous Al$_{86}$Ni$_{8-x}$Co$_{x}$Y$_{6}$ and Al$_{86}$Ni$_{8-x}$Co$_{x}$Gd$_{6}$ ($x = 0, 2, 4, 6, 8$) alloys on structure, thermal stability, mechanism of first stage of crystallization and on microhardness in both amorphous state and nanocomposite one is studied by X-ray diffractometry, differential scanning calorimetry, and microhardness measurement methods. As determined, the increase in the Co content leads to increasing of the onset crystallization temperatures and microhardness of amorphous phases from 477 to 573 K and from 2.97 to 3.11 GPa in Al$_{86}$Ni$_{8-x}$Co$_{x}$Y$_{6}$ alloys, from 496 to 577 K and from 3.23 to 3.4 GPa in Al$_{86}$Ni$_{8-x}$Co$_{x}$Gd$_{6}$ alloys, respectively, and to changing of first stage of crystallization mechanism from one-phase mechanism to two-phase one. As shown, the formation of amorphous—nanocrystalline structures at the first stage of crystallization results in an essential increase of microhardness up to 5.98 $\pm$ 0.07 GPa in Al$_{86}$Ni$_{8-x}$Co$_{x}$Y$_{6}$ alloys and up to 5.0 $\pm$ 0.03 GPa in Al$_{86}$Ni$_{8-x}$Co$_{x}$Gd$_{6}$ alloys. As suggested, the observed changes in thermal stability and microhardness of the amorphous alloys may be caused by the differences in the electronic structure of the alloying rare-earth elements.