Mycobacterium bovis Bacille Calmette-Guerin (BCG) is the only vaccine in use to prevent Mycobacterium tuberculosis (Mtb) infection. Here we analyzed the protective efficacy of BCG against Mtb challenges 21 or 120 days after vaccination. Only after 120 days post-vaccination were mice able to efficiently induce early Mtb growth arrest and maintain long-lasting control of Mtb. This protection correlated with the accumulation of CD4⁺ T cells expressing IL-17⁺TNF⁺IL-2⁺. In contrast, mice challenged with Mtb 21 days after BCG vaccination exhibited only a mild and transient protection, associated with the accumulation of CD4⁺ T cells that were mostly IFN-γ⁺TNF⁺ and to a lesser extent IFN-γ⁺TNF⁺IL-2⁺. These data suggest that the memory response generated by BCG vaccination is functionally distinct depending upon the temporal proximity to BCG vaccination. Understanding how these responses are generated and maintained is critical for the development of novel vaccination strategies against tuberculosis.