A scientific review for the government of the United Kingdom has recommended that the development of a cattle vaccine against bovine tuberculosis holds the best prospects to control this disease in the national herd. As BCG vaccination of cattle results in variable degrees of protection, novel vaccine strategies that could replace or supplement BCG are required. In this study, the mycobacterial antigen HSP65 was used to determine whether priming cattle with a plasmid DNA vaccine and subsequently boosting with the recombinant protein in adjuvant (heterologous prime-boost approach) would result in improved and more homogenous immune responses over immunising with plasmid DNA or protein in adjuvant alone. The results demonstrated that strong, and compared to protein or DNA vaccination protocols alone, more homogenous, cellular immune responses were induced in cattle vaccinated with the prime-boost regimen. In addition, DNA prime-protein boost vaccination as well as protein vaccination resulted in stronger humoral immune responses with a balanced IgG profile compared to DNA vaccination alone. Importantly, none of the vaccination protocols sensitised cattle to the intradermal tuberculin test suggesting that TB subunit vaccines can be designed to allow the continued use of the tuberculin test to discriminate between vaccinated cattle and those infected with Mycobacterium bovis.