Immunological memory is a central feature of the adaptive immune system and a prerequisite for generating effective vaccines. Understanding long-term memory responses to Mycobacterium tuberculosis will thus provide us with valuable insights that can guide us in the search for a novel vaccine against tuberculosis (TB). For many years, triggering CD4 T cells and, in particular, those secreting interferon-γ has been the goal of most TB vaccine research, and numerous data from animals and humans support the key role of this subset in protective immunity. More recently, we have learned that the memory response required for effective control of M. tuberculosis is much more complex, probably involving several phenotypically different CD4 T cell subsets as well as other cell types that are yet to be defined. Herein, we describe recent insights into memory immunity to TB in the context of both animal models and the human infection. With the increasing amount of data generated from clinical testing of novel TB vaccines, we also summarize recent knowledge of vaccine-induced memory immunity.