Early trials of novel vaccines against tuberculosis (TB) in adults have suggested substantial protection against TB. However, little is known about the feasibility and affordability of rolling out such vaccines in practice. We conducted expert interviews to identify plausible vaccination implementation strategies for the novel M72/AS01E vaccine candidate. The strategies were defined in terms of target population, coverage, vaccination schedule and delivery mode. We modelled these strategies to estimate long-term resource requirements and health benefits arising from vaccination over 2025-2050. We presented these to experts who excluded strategies that were deemed infeasible, and estimated cost-effectiveness and budget impact for each remaining strategy. The four strategies modelled combined target populations: either everyone aged 18-50, or all adults living with HIV, with delivery strategies: either a mass campaign followed by routine vaccination of 18-year olds, or two mass campaigns 10 years apart. Delivering two mass campaigns to all 18-50-year olds was found to be the most cost-effective strategy conferring the greatest net health benefit of 1.2 million DALYs averted having a probability of being cost-effective of 65-70%. This strategy required 38 million vaccine courses to be delivered at a cost of USD 507 million, reducing TB-related costs by USD 184 million while increasing ART costs by USD 79 million. A suitably designed adult TB vaccination programme built around novel TB vaccines is likely to be cost-effective and affordable given the resource and budget constraints in South Africa.