OBJECTIVES: Ending HIV by 2030 is a global priority. Achieving this requires alternative HIV testing strategies, such as HIV self-testing (HIVST) to reach all individuals with HIV testing services (HTS). We present the results of a trial evaluating the impact of community-based distribution of HIVST in community and facility settings on the uptake of HTS in rural and urban Zambia. DESIGN: Pair-matched cluster randomised trial. METHODS: In catchment areas of government health facilities, OraQuick HIVST kits were distributed by community-based distributors (CBDs) over 12 months in 2016-2017. Within matched pairs, clusters were randomised to receive the HIVST intervention or standard of care (SOC). Individuals aged ≥16 years were eligible for HIVST. Within communities, CBDs offered HIVST in high traffic areas, door to door and at healthcare facilities. The primary outcome was self-reported recent testing within the previous 12 months measured using a population-based survey. RESULTS: In six intervention clusters (population 148 541), 60 CBDs distributed 65 585 HIVST kits. A recent test was reported by 66% (1622/2465) in the intervention arm compared with 60% (1456/2429) in SOC arm (adjusted risk ratio 1.08, 95% CI 0.94 to 1.24; p=0.15). Uptake of the HIVST intervention was low: 24% of respondents in the intervention arm (585/2493) used an HIVST kit in the previous 12 months. No social harms were identified during implementation. CONCLUSION: Despite distributing a large number of HIVST kits, we found no evidence that this community-based HIVST distribution intervention increased HTS uptake. Other models of HIVST distribution, including secondary distribution and community-designed distribution models, provide alternative strategies to reach target populations. TRIAL REGISTRATION NUMBER: ClinicalTrials.gov Registry (NCT02793804).