Prophylactic efficacy of two different delivery platforms for vaccination against Mycobacterium avium (M. avium) were tested in this study; a subunit and an RNA-based vaccine. The vaccine antigen, ID91, includes four mycobacterial antigens: Rv3619, Rv2389, Rv3478, and Rv1886. We have shown that ID91+GLA-SE is effective against a clinical NTM isolate, M. avium 2–151 smt. Here, we extend these results and show that a heterologous prime/boost strategy with a repRNA-ID91 (replicon RNA) followed by protein ID91+GLA-SE boost is superior to the subunit protein vaccine given as a homologous prime/boost regimen. The repRNA-ID91/ID91+GLA-SE heterologous regimen elicited a higher polyfunctional CD4⁺ T_H1 immune response when compared to the homologous protein prime/boost regimen. More significantly, among all the vaccine regimens tested only repRNA-ID91/ID91+GLA-SE induced IFN-γ and TNF-secreting CD8⁺ T cells. Furthermore, the repRNA-ID91/ID91+GLA-SE vaccine strategy elicited high systemic proinflammatory cytokine responses and induced strong ID91 and an Ag85B-specific humoral antibody response a pre- and post-challenge with M. avium 2–151 smt. Finally, while all prophylactic prime/boost vaccine regimens elicited a degree of protection in beige mice, the heterologous repRNA-ID91/ID91+GLA-SE vaccine regimen provided greater pulmonary protection than the homologous protein prime/boost regimen. These data indicate that a prophylactic heterologous repRNA-ID91/ID91+GLA-SE vaccine regimen augments immunogenicity and confers protection against M. avium.