Background: Adults seeking diagnosis and treatment for tuberculosis (TB) and HIV in low-resource settings face considerable barriers and have high pre-treatment mortality. Efforts to improve access to prompt TB treatment have been hampered by limitations in TB diagnostics, with considerable uncertainty about how available and new tests can best be implemented. Design and methods: The PROSPECT Study is an open, three-arm pragmatic randomised study that will investigate the effectiveness and cost-effectiveness of optimised HIV and TB diagnosis and linkage to care interventions in reducing time to TB diagnosis and prevalence of undiagnosed TB and HIV in primary care in Blantyre, Malawi. Participants (≥ 18 years) attending a primary care clinic with TB symptoms (cough of any duration) will be randomly allocated to one of three groups: (i) standard of care; (ii) optimised HIV diagnosis and linkage; or (iii) optimised HIV and TB diagnosis and linkage. We will test two hypotheses: firstly, whether prompt linkage to HIV care should be prioritised for adults with TB symptoms; and secondly, whether an optimised TB triage testing algorithm comprised of digital chest x-ray evaluated by computer-aided diagnosis software and sputum GeneXpert MTB/Rif can outperform clinician-directed TB screening. The primary trial outcome will be time to TB treatment initiation by day 56, and secondary outcomes will include prevalence of undiagnosed TB and HIV, mortality, quality of life, and cost-effectiveness. Conclusions: The PROSPECT Study will provide urgently-needed evidence under "real-life" conditions to inform clinicians and policy makers on how best to improve TB/HIV diagnosis and treatment in Africa. Clinical trial registration: NCT03519425 (08/05/2018).