Vaccination for the control of bovine tuberculosis (bTB) in cattle is not currently used within any international control program, and is illegal within the EU. Candidate vaccines, based upon Mycobacterium bovis bacillus Calmette-Guérin (BCG) all interfere with the action of the tuberculin skin test, which is used to determine if animals, herds and countries are officially bTB-free. New diagnostic tests that Differentiate Infected from Vaccinated Animals (DIVA) offer the potential to introduce vaccination within existing eradication programs. We use within-herd transmission models estimated from historical data from Great Britain (GB) to explore the feasibility of such supplemental use of vaccination. The economic impact of bovine Tuberculosis for farmers is dominated by the costs associated with testing, and associated restrictions on animal movements. Farmers' willingness to adopt vaccination will require vaccination to not only reduce the burden of infection, but also the risk of restrictions being imposed. We find that, under the intensive sequence of testing in GB, it is the specificity of the DIVA test, rather than the sensitivity, that is the greatest barrier to see a herd level benefit of vaccination. The potential negative effects of vaccination could be mitigated through relaxation of testing. However, this could potentially increase the hidden burden of infection within Officially TB Free herds. Using our models, we explore the range of the DIVA test characteristics necessary to see a protective herd level benefit of vaccination. We estimate that a DIVA specificity of at least 99.85% and sensitivity of >40% is required to see a protective benefit of vaccination with no increase in the risk of missed infection. Data from experimentally infected animals suggest that this target specificity could be achieved in vaccinates using a cocktail of three DIVA antigens while maintaining a sensitivity of 73.3% (95%CI: 61.9, 82.9%) relative to post-mortem detection.