To more closely understand the mechanisms of how BCG vaccination confers immunity would help to rationally design improved tuberculosis vaccines that are urgently required. Given the established central role of CD4 T cells in BCG induced immunity, we sought to characterise the generation of memory CD4 T cell responses to BCG vaccination and M. bovis infection in a murine challenge model. We demonstrate that a single systemic BCG vaccination induces distinct systemic and mucosal populations of T effector memory (TEM) cells in vaccinated mice. These CD4+CD44hiCD62LloCD27- T cells concomitantly produce IFN-γ and TNF-α, or IFN-γ, IL-2 and TNF-α and have a higher cytokine median fluorescence intensity MFI or 'quality of response' than single cytokine producing cells. These cells are maintained for long periods (>16 months) in BCG protected mice, maintaining a vaccine-specific functionality. Following virulent mycobacterial challenge, these cells underwent significant expansion in the lungs and are, therefore, strongly associated with protection against M. bovis challenge. Our data demonstrate that a persistent mucosal population of TEM cells can be induced by parenteral immunization, a feature only previously associated with mucosal immunization routes; and that these multifunctional TEM cells are strongly associated with protection. We propose that these cells mediate protective immunity, and that vaccines designed to increase the number of relevant antigen-specific TEM in the lung may represent a new generation of TB vaccines.