Background There is a high incidence of tuberculosis (TB) early after antiretroviral therapy (ART) initiation. This historical cohort study evaluated the association of efavirenz (EFV) compared to nevirapine (NVP) with post-ART TB among patients initiated on first-line ART from 2005 to 2009 in a large, urban HIV clinic in Uganda. Methods Hazard ratios (HR) for developing TB were computed using multivariable Cox proportional hazards models with inverse weighting of the probability of being prescribed NVP or EFV (calculated by a multi-variable logistic regression model), stratifying by baseline CD4+ T-cell count. Adjustment for time-updated CD4+ T-cell count, restriction of the analysis to patients remaining in follow-up and a TB-free survival analysis were performed as sensitivity analyses. Results ART was initiated in 5,797 patients; 66% were women with a mean age of 37 years (sd 9) and a median baseline CD4+ T-cell count of 117 cells/mm3 (IQR 43–182). Overall, 60% ( n=3,484) were initiated on NVP and 40% ( n=2,313) on EFV. In the first 2 years of ART, 377 patients developed TB. The use of EFV compared to NVP was independently associated with higher TB incidence in patients with a baseline CD4+ T-cell count <100 cells/mm3 (HR 2.05 [95% CI 1.29, 3.27]; P=0.003), but not at higher CD4+ T-cell counts (HR 0.71 [95% CI 0.39, 1.31]; P=0.428). These estimates were robust to all sensitivity analyses. Conclusions There was a higher incidence of TB in patients with baseline CD4+ T-cell counts <100 cells/mm3 initiated on EFV compared to those initiated on NVP. Further research in a trial setting or a larger multisite observational cohort is needed to confirm these findings.