Bovine tuberculosis, caused by Mycobacterium bovis, is rapidly increasing in cattle herds in developed countries such as the UK, New Zealand and the USA. In addition, persistence of M. bovis in other parts of the world may account for up to 10% of cases of human tuberculosis. Thus, a rise in the number of M. bovis infections poses an increased human health risk and is also a major economic problem. In the UK, the incidence of bovine tuberculosis continues to rise despite the use of a skin test and slaughter control policy, highlighting the need for an effective vaccination strategy to control the spread of disease. The only vaccine currently available for human, (and bovine), tuberculosis is Bacillus Calmette-Guérin, which is known to have variable efficacy for both species. In this article, the authors discuss potential strategies by which Bacillus Calmette-Guérin vaccination may be improved to allow highly efficacious vaccination of cattle. These strategies are also highly applicable to the fight against tuberculosis in humans.