Background: The long-term (5 year) effect of early initiation of antiretroviral therapy (ART) versus delayed initiation of ART on immune recovery and risk for tuberculosis (TB) infection in HIV-1 infected individuals is not certain. Methodology: We conducted an open label randomized controlled trial of immediate initiation of ART in HIV-infected adults with CD4 counts between 200 and 350 cells/mm3 versus deferring ART until the CD4 count was below 200. The primary comparisons were CD4 counts over time and the risk for incident TB during 5 years of follow-up. Generalized estimating equations were used to compare CD4 counts between groups, probability of TB-free survival was calculated using Kaplan-Meier survival methods. Univariate and multivariate Cox proportional hazards regression models were used to estimate the risk of TB as hazard ratios (HR) with 95% confidence intervals. The trial is registered at ClinicalTrials.gov with study number NCT00120510. Results: 816 participants were enrolled, 408 in each treatment arm. The median age was 40 and 58% of participants were women. The early group started ART within 2 weeks, the deferred group started ART a median of 1.3 years after enrollment. After 5 years, the mean CD4 count in the early group was significantly higher than in the deferred group; 574 cells/mm3 (95% confidence interval [CI] 545 to 603) versus 451 cells/mm3 (95% CI 419 to 484; p<0.0001). Risk for incident TB was significantly higher in the deferred group five years after randomization (hazard ratio [HR] 2.44 [95% CI 1.56-3.70]; p<0.0001). In a time dependent multivariate analysis, TB risk correlated with lower CD4 counts and with lower Body Mass Index. For each CD4 decrease of 50 cells/mm3 the hazards of incident TB increased by 1.30 (95% CI 1.16-1.43; p<0.0001). Conclusions: Short delays in ART initiation for HIV-infected adults with CD4 counts of 200 - 350 cells/mm3 can result in long-term (5 year) immune dysfunction and persistent increased risk of tuberculosis.