Bacille-Calmette-Guérin (BCG) is the only approved vaccine against Mycobacterium tuberculosis (MTB), offering protection not only against tuberculosis (TB) but also non-related infections. 'Trained immunity' of innate immune cells is considered one of the mechanisms of this broad protection derived through BCG. Here, we investigated the effect of BCG on Natural Killer (NK) cells, a key innate immune cell type, and their subsequent responses to mycobacterial and HIV antigens. We found that BCG-induced KLRG1+ NK cells exhibit significantly higher production of IFNγ, compared to KLRG1- cells, indicating their memory-like responses upon exposure to these antigens (p < 0.05). These findings may be important in regions of high burden of HIV and TB where BCG is routinely administered.