BACKGROUND: Tuberculosis, which is often undiagnosed, is the major cause of death among HIV-positive people. We aimed to test whether the use of a clinical algorithm enabling the initiation of empirical tuberculosis treatment by nurses in primary health-care clinics would reduce mortality compared with standard of care for adults with advanced HIV disease. METHODS: In this open-label cluster-randomised controlled trial, we recruited individuals from 24 primary health-care clinics in South Africa. The clinics were randomly assigned (1:1) to either deliver an intervention or routine care (control) using computer-generated random numbers. Eligible participants were HIV-positive adults (aged ≥18 years) with CD4 counts of 150 cells per μL or less, who had not had antiretroviral therapy (ART) in the past 6 months or tuberculosis treatment in the past 3 months, and did not require urgent hospital referral. In intervention clinics, study nurses assessed participants on the basis of tuberculosis symptoms, body-mass index, point-of-care haemoglobin concentrations, and urine lipoarabinomannan assay results. Participants classified by a study algorithm as having high probability of tuberculosis (positive urine lipoarabinomannan assay, body-mass index <18·5 kg/m2, or haemoglobin concentration <100 g/L) were recommended to start tuberculosis treatment immediately followed by ART 2 weeks later; participants classified as medium probability (tuberculosis symptoms, no high probability criteria) were recommended to have symptom-guided investigation; and participants classified as low probability (no tuberculosis symptoms or high probability criteria) were recommended to start ART immediately. In standard-of-care clinics, participants received treatment in accordance with South African guidelines. Investigators and participants were aware of treatment allocation. The primary outcome was all-cause mortality at 6 months, assessed in the intention-to-treat population. Safety was also analysed in the intention-to treat population. This trial is registered with the ISRCTN registry, ISRCTN35344604, and the South African National Clinical Trials Register, DOH-27-0812-3902. FINDINGS: Between Dec 19, 2012, and Dec 18, 2014, 3091 individuals were screened for eligibility, of whom 3053 were recruited, and 3022 (1507 participants in the intervention group and 1515 participants in the control group) were analysed for the primary outcome. 930 (61·7%) of 1507 participants in the intervention group versus 172 (11·4%) of 1515 participants in the control group had started tuberculosis treatment by 2 months. At 6 months, the mortality rate was 19·0 deaths per 100 person-years for the intervention group versus 21·6 deaths per 100 person-years in the control group (unadjusted hazard ratio [HR] 0·92, 95% CI 0·67-1·26, p=0·58; adjusted HR 0·87, 0·61-1·24, p=0·41). 28 (1·9%) of 1507 participants in the intervention group and ten (0·7%) of 1515 participants in the control group reported serious or severe adverse events. Grade 3 or 4 nausea and vomiting was the most common adverse event (ten participants in the intervention group and four participants in the control group). Among participants with adverse events, eight participants (six participants in the intervention group and two participants in the control group) died; none of the six deaths in the intervention group were attributed to the study intervention. INTERPRETATION: Our intervention substantially increased coverage of tuberculosis treatment in this high-risk population, but did not reduce mortality. FUNDING: Joint Global Health Trials (Medical Research Council, Department for International Development, Wellcome Trust).