In a number of clinical studies the current TB vaccine, Mycobacterium bovis bacille Calmette-Guérin (BCG), has provided little or no protection against pulmonary tuberculosis in cattle and man. A new generation of vaccines is therefore required to replace or supplement BCG. Safety concerns surrounding a number of strategies make protein subunits an attractive approach. Moreover, novel prime-boost strategies based on primary immunisations with BCG are not only showing promise but also present a clear strategy for testing new TB vaccines in clinical studies. We report the evaluation of six protein vaccine candidates for their ability to induce protective immunity in a murine virulent M. bovis challenge model. One protein (Rv3019c) induced reproducibly significant protection in the spleen and lungs approaching that induced by BCG. Detailed analysis of antigen-specific T cell responses revealed that despite robust responses in the spleen and lungs of vaccinated mice, there was no correlation between these responses and the protective efficacy of the vaccine. Significantly, Rv3019c also stimulated IFN-γ responses in PBMC from BCG vaccinated cattle, indicating its potential for use in a heterologous prime-boost strategy in conjunction with BCG in the target species.