Heterologous prime-boost immunization strategies can evoke powerful T cell immune responses and may be of value in developing an improved tuberculosis vaccine. We show that recombinant modified vaccinia virus Ankara, expressing Mycobacterium tuberculosis Ag 85A (M. 85A), strongly boosts bacille Calmette-Guérin (BCG)-induced Ag 85A specific CD4+ and CD8+ T cell responses in mice. A comparison of intranasal (in) and parenteral immunization of BCG showed that while both routes elicited comparable T cell responses in the spleen, only in delivery elicited specific T cell responses in the lung lymph nodes, and these responses were further boosted by in delivery of M. 85A. Following aerosol challenge with M. tuberculosis, in boosting of BCG with either BCG or M. 85A afforded unprecedented levels of protection in both the lungs (2.5 log) and spleens (1.5 log) compared with naive controls. Protection in the lung correlated with the induction of Ag 85A-specific, IFN-γ-secreting T cells in lung lymph nodes. These findings support further evaluation of mucosally targeted prime-boost vaccination approaches for tuberculosis.