Al-Rare Earth (RE) metallic glasses provide an effective model system to study the effect of nanocrystallites in an amorphous matrix on nanomechanical behavior. In this work, we achieved a series of Al-Tb metallic glass-crystalline composites with systematically varying crystalline content through annealing. The nanomechanical properties were characterized using micropillar compression tests and nanoindentation for as-quenched amorphous and annealed amorphous/nanocrystalline composite specimens. The promising hardness increases after annealing from 3.0 GPa to 4.6 GPa and elastic modulus increment from 68 GPa to 92 GPa were discussed in detail, considering the structural features of Al-RE marginal metallic glass formers. The increase in elastic modulus is associated with the nucleated fcc-Al nanocrystals that divide the amorphous matrix, leading to the branching of the shear bands. The correlation between the fcc-Al nanocrystals and the behavior of shear bands was discussed in detail.