Novel immunization strategies are needed to enhance the global control of tuberculosis (TB). In this study, we assessed the immunizing activity of a recombinant modified vaccinia Ankara (MVA) construct (MVA/IL-15/5Mtb) which overexpresses five Mycobacterium tuberculosis antigens (antigen 85A, antigen 85B, ESAT6, HSP60, and Mtb39), as well as the molecular adjuvant interleukin-15 (IL-15). Homologous prime/boost studies showed that the MVA/IL-15/5Mtb vaccine induced moderate but highly persistent protective immune responses for at least 16 months after the initial vaccination and that the interval between the prime and boost did not significantly alter vaccine-induced antituberculosis protective immunity. At 16 months, when the Mycobacterium bovis BCG and MVA/IL-15/5Mtb vaccine-induced protection was essentially equivalent, the protective responses after a tuberculous challenge were associated with elevated levels of gamma interferon (IFN-gamma), IL-17F, Cxcl9, and Cxcl10. To amplify the immunizing potential of the MVA/IL-15/5Mtb vaccine, a heterologous prime/boost regimen was tested using an ESAT6-antigen 85B (E6-85) fusion protein formulated in dimethyldiotacylammonium bromide/monophosphoryl lipid A (DDA/MPL) adjuvant as the priming vaccine and the MVA/IL-15/5Mtb recombinant virus as the boosting agent. When MVA/IL-15/5Mtb vaccine boosting was done at 2 or 6 months following the final fusion protein injections, the prime/boost regimen evoked protective responses against an aerogenic M. tuberculosis challenge which was equivalent to that induced by BCG immunization. Long-term memory after immunization with the E6-85-MVA/IL-15/5Mtb combination regimen was associated with the induction of monofunctional CD4 and CD8 IFN-gamma-producing T cells and multifunctional CD4 and CD8 T cells expressing IFN-gamma/tumor necrosis factor alpha (TNF-alpha), TNF-alpha/IL-2, and IFN-gamma/TNF-alpha/IL-2. In contrast, BCG-induced protection was characterized by fewer CD4 and CD8 monofunctional T cells expressing IFN-gamma and only IFN-gamma/TNF-alpha and IFN-gamma/TNF-alpha/IL-2 expressing multifunctional T (MFT) cells. Taken together, these results suggest that a heterologous prime/boost protocol using an MVA-based tuberculosis vaccines to boost after priming with TB protein/adjuvant preparations should be considered when designing long-lived TB immunization strategies.