HIV has fuelled increasing tuberculosis (TB) incidence in sub-Saharan Africa. Better control of TB in this region may be achieved directly through TB programme improvements and indirectly through expanded use of antiretroviral therapy (ART) among those with HIV. We used a mathematical model of TB and HIV in South Africa to examine the potential epidemiological impact in scenarios involving improvements in three dimensions of TB programmes: coverage, diagnosis and treatment effectiveness, as well as expanded ART use through broadened eligibility. We projected the effect of alternative scenarios on TB prevalence, incidence and TB-related mortality over 20 years. Of the three dimensions of TB programme improvement, expanding coverage would produce the greatest reduction in TB burden. Compared with current performance, combined TB programme improvements were projected to decrease TB incidence by 30% over 5 years and 46% over 20 years, and decrease TB-related mortality by 45% over 5 years and 69% over 20 years. Expanded ART eligibility was projected to decrease TB incidence by 22% over 5 years and 45% over 20 years, and TB-related mortality by 22% over 5 years and 50% over 20 years. We found that over a 20-year horizon, TB-specific and HIV-specific programme changes contribute equally to incidence reductions, whereas the TB-specific changes produce a majority of the mortality benefits. An aggressive expansion of ART alongside traditional TB-specific control measures has the potential to greatly reduce TB burden, with the different elements of a combined approach having a synergistic effect in reducing long-term TB incidence and mortality.