Objective: EMOD-HIV v0.8 has been used to estimate the potential impact of expanding treatment guidelines to allow earlier initiation of antiretroviral therapy (ART) in sub-Saharan Africa with current or improved treatment coverage. In generating these results, a model must additionally make assumptions about the rates of dropout and re-initiation into ART programs before and after the program change, about which little is known. The objective of this work is to rigorously analyze modeling assumptions and the sensitivity of model results with respect to relevant mechanisms and parameters., Methods: We varied key model assumptions pertaining to ART dropout and re-enrollment to analyze their effect on the cost, impact, and cost-effectiveness of expanding treatment guidelines, and of expanding coverage via improved testing and linkage to care. Additionally, we performed a sensitivity analysis of 17 relevant model parameters., Setting: South Africa., Results: Allowing re-initiation of ART irrespective of prior treatment doubled the cost and impact of expanding treatment guidelines, as compared with a scenario in which re-initiation could only be triggered by a health event (AIDS symptoms, diagnosis of a partner, or an antenatal care visit). Increasing the probability of 'voluntary' re-initiation (not triggered by a health event) was the most cost-effective way to improve the treatment program, especially in the short term because it provided immediate benefits to those who would otherwise have delayed re-initiation until the onset of AIDS symptoms. However, the maximum impact of this change was limited compared with expanding coverage through improvements in testing and linkage to care. Beyond improvements in coverage and re-initiation, further gains could be made by improving retention in care. Only with optimal retention in care was expansion of guidelines cost-saving after 20 years due to reductions in transmission. Re-initiation did not reduce transmission sufficiently to make a guideline change cost-effective due to transmission that occurred while patients were away from care. Sensitivity analysis suggested that enormous health benefits could be attained by improving treatment regimens to have higher efficacy at preventing transmission, increasing the proportion of the population with access to improved healthcare, and reducing 'leaks' in the 'cascade of care.' Increasing the proportion of individuals who receive CD4 cell results was particularly cost-effective at baseline levels of coverage, and increasing retention on ART was particularly cost-effective with expanded coverage., Conclusion: This analysis provides a sense of the magnitude of uncertainty in program cost and impact that policy-makers could anticipate in the face of uncertain future programmatic changes. Our findings suggest that increasing re-initiation is the most cost-effective means of initial program improvement, especially in the short term, but that improvements in retention are necessary in order to reap the full transmission-blocking benefits of a test-and-treat program in the long term.