BACKGROUND: Uganda changed its antiretroviral therapy guidelines in 2014, increasing the CD4 threshold for antiretroviral therapy initiation from 350 cells/μl to 500 cells/μl. We investigate what effect this change in policy is likely to have on HIV incidence, morbidity, and programme costs, and estimate the cost-effectiveness of the change over different time horizons. METHODS: We used a complex individual-based model of HIV transmission and antiretroviral therapy scale-up in Uganda. 100 model fits were generated by fitting the model to 51 demographic, sexual behaviour, and epidemiological calibration targets, varying 96 input parameters, using history matching with model emulation. An additional 19 cost and disability weight parameters were varied during the analysis of the model results. For each model fit, the model was run to 2030, with and without the change in threshold to 500 cells/μl. RESULTS: The change in threshold led to a 9.7% (90% plausible range: 4.3%-15.0%) reduction in incidence in 2030, and averted 278,944 (118,452-502,790) DALYs, at a total cost of $28M (-$142M to +$195M). The cost per disability adjusted life year (DALY) averted fell over time, from $3238 (-$125 to +$29,969) in 2014 to $100 (-$499 to +$785) in 2030. The change in threshold was cost-effective (cost <3×Uganda's per capita GDP per DALY averted) by 2018, and highly cost-effective (cost <Uganda's per capita GDP per DALY averted) by 2022, for more than 50% of parameter sets. CONCLUSIONS: Model results suggest that the change in threshold is unlikely to have been cost-effective to date, but is likely to be highly cost-effective in Uganda by 2030. The time horizon needs to be chosen carefully when projecting intervention effects. Large amounts of uncertainty in our results demonstrates the need to comprehensively incorporate uncertainties in model parameterisation.