BACKGROUND: HIV self-testing allows HIV testing at any place and time and without health workers. HIV self-testing may thus be particularly useful for female sex workers (FSWs), who should test frequently but face stigma and financial and time barriers when accessing healthcare facilities. METHODS AND FINDINGS: We conducted a cluster-randomized controlled health systems trial among FSWs in Kampala, Uganda, to measure the effect of 2 HIV self-testing delivery models on HIV testing and linkage to care outcomes. FSW peer educator groups (1 peer educator and 8 participants) were randomized to either (1) direct provision of HIV self-tests, (2) provision of coupons for free collection of HIV self-tests in a healthcare facility, or (3) standard of care HIV testing. We randomized 960 participants in 120 peer educator groups from October 18, 2016, to November 16, 2016. Participants' median age was 28 years (IQR 24-32). Our prespecified primary outcomes were self-report of any HIV testing at 1 month and at 4 months; our prespecified secondary outcomes were self-report of HIV self-test use, seeking HIV-related medical care and ART initiation. In addition, we analyzed 2 secondary outcomes that were not prespecified: self-report of repeat HIV testing-to understand the intervention effects on frequent testing-and self-reported facility-based testing-to quantify substitution effects. Participants in the direct provision arm were significantly more likely to have tested for HIV than those in the standard of care arm, both at 1 month (risk ratio [RR] 1.33, 95% CI 1.17-1.51, p < 0.001) and at 4 months (RR 1.14, 95% CI 1.07-1.22, p < 0.001). Participants in the direct provision arm were also significantly more likely to have tested for HIV than those in the facility collection arm, both at 1 month (RR 1.18, 95% CI 1.07-1.31, p = 0.001) and at 4 months (RR 1.03, 95% CI 1.01-1.05, p = 0.02). At 1 month, fewer participants in the intervention arms had sought medical care for HIV than in the standard of care arm, but these differences were not significant and were reduced in magnitude at 4 months. There were no statistically significant differences in ART initiation across study arms. At 4 months, participants in the direct provision arm were significantly more likely to have tested twice for HIV than those in the standard of care arm (RR 1.51, 95% CI 1.29-1.77, p < 0.001) and those in the facility collection arm (RR 1.22, 95% CI 1.08-1.37, p = 0.001). Participants in the HIV self-testing arms almost completely replaced facility-based testing with self-testing. Two adverse events related to HIV self-testing were reported: interpersonal violence and mental distress. Study limitations included self-reported outcomes and limited generalizability beyond FSWs in similar settings. CONCLUSIONS: In this study, HIV self-testing appeared to be safe and increased recent and repeat HIV testing among FSWs. We found that direct provision of HIV self-tests was significantly more effective in increasing HIV testing among FSWs than passively offering HIV self-tests for collection in healthcare facilities. HIV self-testing could play an important role in supporting HIV interventions that require frequent HIV testing, such as HIV treatment as prevention, behavior change for transmission reduction, and pre-exposure prophylaxis. TRIAL REGISTRATION: ClinicalTrials.gov NCT02846402.