Background Early mortality for HIV-positive people starting antiretroviral therapy (ART) remains high in resource-limited settings, with tuberculosis the most important cause. Existing rapid diagnostic tests for tuberculosis lack sensitivity among HIV-positive people, and consequently, tuberculosis treatment is either delayed or started empirically (without bacteriological confirmation). We developed a management algorithm for ambulatory HIV-positive people, based on body mass index and point-of-care tests for haemoglobin and urine lipoarabinomannan (LAM), to identify those at high risk of tuberculosis and mortality. We designed a clinical trial to test whether implementation of this algorithm reduces six-month mortality among HIV-positive people with advanced immunosuppression. Methods/design The TB Fast Track study is an open, pragmatic, cluster randomised superiority trial, with 24 primary health clinics randomised to implement the intervention or standard of care. Adults (aged ≥18 years) with a CD4 count of 150 cells/μL or less, who have not received any tuberculosis treatment in the last three months, or ART in the last six months, are eligible. In intervention clinics, the study algorithm is used to classify individuals as at high, medium or low probability of tuberculosis. Those classified as high probability start tuberculosis treatment immediately, followed by ART after two weeks. Medium-probability patients follow the South African guidelines for test-negative tuberculosis and are reviewed within a week, to be re-categorised as low or high probability. Low-probability patients start ART as soon as possible. The primary outcome is all-cause mortality at six months. Secondary outcomes include severe morbidity, time to ART start and cost-effectiveness. Discussion This trial will test whether a primary care-friendly management algorithm will enable nurses to identify HIV-positive patients at the highest risk of tuberculosis, to facilitate prompt treatment and reduce early mortality. There remains an urgent need for better diagnostic tests for tuberculosis, especially for people with advanced HIV disease, which may render empirical treatment unnecessary. Trial registration This trial was registered with Current Controlled Trials (identifier: ISRCTN35344604) on 12 September 2012.