Early mortality after initiation of antiretroviral therapy (ART) occurs in 9-39% of patients in sub-Saharan Africa. A significant proportion of deaths are attributable to tuberculosis (TB). Low baseline CD4 T-cell count and low body mass index (BMI) are strongly associated with early mortality. We hypothesized that initiation of ART concurrent with presumptive anti-TB chemotherapy in high-risk patients would reduce mortality within the first 6 months by treating unrecognized TB. From October 2011 to December 2012, ART-naive, smear-negative participants with a CD4 T-cell count textless 50 cells/μL and BMI textless 18 kg/m(2) were randomly assigned to undergo either empiric four-drug anti-TB treatment followed 2 weeks later by efavirenz-based ART (N = 23) (ART + TB) or ART only (N = 20). This open-label, 1:1 randomized, controlled trial took place in Uganda, Mozambique, and Gabon and was stopped prematurely by the sponsor for slow recruitment. Overall, the 43 participants had a median CD4 of 22 (interquartile range [IQR]: 9-35) cells/μL and a median BMI of 17.5 (IQR: 16.6-18.0) kg/m(2) The mortality was 14% (95% confidence interval [CI]: 5.3-27.9); two (10.0%) participants (ART-only group), and four (17.4%; ART + TB group). The associated hazard ratio (HR) for all-cause mortality was 1.6 (95% CI: 0.30-8.90). Despite limited enrollment, the study did not suggest that empiric TB treatment in severely immunosuppressed patients with low BMI decreased mortality and, had an HR in the opposite direction than expected. Notably, two participants in the ART + TB group died with autopsy-confirmed drug-induced hepatotoxicity. Improved TB diagnostics sensitive in immunosuppressed patients presenting late to care are urgently needed for more targeted interventions.