Natural killer (NK) cells are lymphocytes of the innate immune system, which play an important role in the initial defense against a wide variety of pathogens, including viruses and intracellular bacteria. NK cells produce cytokines that enhance immune responses directed toward pathogens and also exert cytotoxic activity against infected cells, thereby eliminating the reservoir of infection. Their role in defense against Mycobacterium tuberculosis (Mtb) has been recently studied, and there is increasing evidence that highlight the importance of NK cell function during pulmonary tuberculosis (PTB), especially in the absence of optimal T-cell responses. Additionally, in the last years, it has been observed that NK cells mediate secondary responses against antigens to which they were previously exposed, an ability classically attributed to lymphocytes of the adaptive branch of immunity. This phenomenon, called “innate memory,” could have important implications in the efforts to develop therapies and vaccines to improve the initial phases of immune reactions against different microorganisms, especially those to which there is not yet available vaccines to prevent infection, as is the case for tuberculosis. Therefore, the possibility of inducing memory-like NK cells ready to act prior to contact with Mtb or during the earliest stages of infection becomes quite interesting. However, our understanding of the mechanisms of innate memory remains incomplete. Here, we review recent literature about the mechanisms involved in the formation and maintenance of NK cell memory and the role of these cells in the immune response during tuberculosis. Finally, we discuss if the current evidence is sufficient to substantiate that NK cells exert more rapid and robust secondary responses after consecutive encounters with Mtb.