Technical Abstract: Previous work in small animal laboratory models of tuberculosis have shown that vaccination strategies based on heterologous prime-boost protocols using Mycobacterium bovis bacille Calmette-Guerin (BCG) to prime and Modified Vaccinia Ankara strain (MVA85A) or recombinant attenuated adenoviruses (Ad85A) expressing the mycobacterial antigen Ag85A to boost may increase the protective efficacy of BCG. Here we report the first efficacy data using these vaccines in cattle, a natural target species of tuberculous infection. Either Ad85A or MVA85A boosting resulted in protection superior to BCG alone. Analysis of vaccine-induced immunity identified memory responses measured by cultured ELISPOT as well as in vitro IL-17 production as predictors of vaccination success. In summary, this study provides the first evidence of improved protection against tuberculosis by viral booster vaccination in a natural target species, and has prioritised potential correlates of vaccine efficacy for further evaluation. These findings also have implications for human TB vaccine development.