Background: Few studies have evaluated the mortality rate in individuals with HIV initiating antiretroviral therapy (ART), undergoing screening with combined or repeated rapid tests for tuberculosis (TB). Methods: All individuals with HIV starting ART, irrespective of the presence of TB-related symptoms, received two consecutive Xpert tests plus a rapid test for the detection of mycobacterial lipoarabinomannan in urine (LAM). Mortality was evaluated by Kaplan–Meier analysis using the log-rank test in univariate analyses and Cox regression models with time-dependent covariates in multivariate analyses. Results: Among 972 individuals screened with combined tests, 98 (10.1%) tested positive for TB with Xpert, LAM, or both. At the end of the study, 780 (80.2%) had completed 2 years of follow-up, 39 (4.0%) had died, and 153 (15.7%) were lost to follow-up. In the multivariate analyses, the factors significantly associated with mortality were missed ART (hazard ratio (HR) 7.05, 95% confidence interval (CI) 2.33–21.35), symptomatic HIV disease (WHO-HIV stage >1) (HR 3.31, 95% CI 1.28–8.54), and low CD4 count (<200/mm3) (HR 2.72, 95% CI 1.21–6.13), with no significant effect of TB status. In the subgroup of the 98 TB-positive individuals, only missed ART (HR 4.12, 95% CI 1.03–16.46) and missed anti-TB treatment (HR 9.25, 95% CI 2.65–32.28) were significantly associated with mortality. Conclusions: A low mortality rate was observed among individuals with HIV undergoing systematic testing for TB at initiation of ART. After adjusting for confounders, mortality was significantly associated with missed ART, advanced disease, and missed anti-TB treatment. These findings reinforce the need to promote early diagnosis of HIV and the adoption of screening strategies for TB that prevent presentation with severe disease.