BACKGROUND: Suboptimal tuberculosis (TB) diagnostics and HIV contribute to the high global burden of TB. We investigated costs and yield from systematic HIV-TB screening, including computer-aided digital chest X-ray (DCXR-CAD). METHODS AND FINDINGS: In this open, three-arm randomised trial, adults (≥18 years) with cough attending acute primary services in Malawi were randomised (1:1:1) to standard of care (SOC); oral HIV testing (HIV screening) and linkage to care; or HIV testing and linkage to care plus DCXR-CAD with sputum Xpert for high CAD4TBv5 scores (HIV-TB screening). Participants and study staff were not blinded to intervention allocation, but investigator blinding was maintained until final analysis. The primary outcome was time to TB treatment. Secondary outcomes included proportion with same-day TB treatment; prevalence of undiagnosed/untreated bacteriologically confirmed TB on day 56; and undiagnosed/untreated HIV. Analysis was done on an intention-to-treat basis. Cost-effectiveness analysis used a health-provider perspective. Between 15 November 2018 and 27 November 2019, 8,236 were screened for eligibility, with 473, 492, and 497 randomly allocated to SOC, HIV, and HIV-TB screening arms; 53 (11%), 52 (9%), and 47 (9%) were lost to follow-up, respectively. At 56 days, TB treatment had been started in 5 (1.1%) SOC, 8 (1.6%) HIV screening, and 15 (3.0%) HIV-TB screening participants. Median (IQR) time to TB treatment was 11 (6.5 to 38), 6 (1 to 22), and 1 (0 to 3) days (hazard ratio for HIV-TB versus SOC: 2.86, 1.04 to 7.87), with same-day treatment of 0/5 (0%) SOC, 1/8 (12.5%) HIV, and 6/15 (40.0%) HIV-TB screening arm TB patients (p = 0.03). At day 56, 2 SOC (0.5%), 4 HIV (1.0%), and 2 HIV-TB (0.5%) participants had undiagnosed microbiologically confirmed TB. HIV screening reduced the proportion with undiagnosed or untreated HIV from 10 (2.7%) in the SOC arm to 2 (0.5%) in the HIV screening arm (risk ratio [RR]: 0.18, 0.04 to 0.83), and 1 (0.2%) in the HIV-TB screening arm (RR: 0.09, 0.01 to 0.71). Incremental costs were US$3.58 and US$19.92 per participant screened for HIV and HIV-TB; the probability of cost-effectiveness at a US$1,200/quality-adjusted life year (QALY) threshold was 83.9% and 0%. Main limitations were the lower than anticipated prevalence of TB and short participant follow-up period; cost and quality of life benefits of this screening approach may accrue over a longer time horizon. CONCLUSIONS: DCXR-CAD with universal HIV screening significantly increased the timeliness and completeness of HIV and TB diagnosis. If implemented at scale, this has potential to rapidly and efficiently improve TB and HIV diagnosis and treatment. TRIAL REGISTRATION: clinicaltrials.gov NCT03519425.