Mycobacterium bovis bacille Calmette-Guérin (BCG) is the most widely used live attenuated vaccine. However, the correlates of protection and waning of its immunity against tuberculosis is poorly understood. In this study, we correlated the longitudinal changes in the magnitude and functional quality of CD4+ and CD8+ T-cell response over a period of two years after mucosal or parenteral BCG vaccination with the strength of protection against Mycobacterium tuberculosis in mice. The BCG vaccination-induced CD4+ and CD8+ T cells exhibited comparable response kinetics but distinct functional attributes in-terms of IFN-γ, IL-2 and TNF-α co-production and CD62L memory marker expression. Despite a near life-long BCG persistence and the induction of enduring CD4+ T-cell responses characterized by IFN-γ and/or TNF-α production with comparable protection, the protective efficacy waned regardless of the route of vaccination. The progressive decline in the multifactorial functional abilities of CD4+ and CD8+ T cells in-terms of type-1 cytokine production, proliferation and cytolytic potential corresponded with the waning of protection against M. tuberculosis infection. In addition, simultaneous increase in the dysfunctional and terminally-differentiated T cells expressing CTLA-4, KLRG-1 and IL-10 during the contraction phase of BCG-induced response coincided with the loss of protection. Our results question the empirical development of BCG-booster vaccines and emphasize the pursuit of strategies that maintain superior T-cell functional capacity. Furthermore, our results underscore the importance of understanding the comprehensive functional dynamics of antigen-specific T-cell responses in addition to cytokine polyfunctionality in BCG-vaccinated hosts while optimizing novel vaccination strategies against tuberculosis.