BACKGROUND: HIV self-testing (HIVST) has been shown to be acceptable, feasible and effective in increasing HIV testing uptake. Novel testing strategies are critical to achieving the UNAIDS target of 95% HIV-positive diagnosis by 2025 in South Africa and globally. METHODS: We modelled the impact of six HIVST kit distribution modalities (community fixed-point, taxi ranks, workplace, partners of primary healthcare (PHC) antiretroviral therapy (ART) patients), partners of pregnant women, primary PHC distribution) in South Africa over 20 years (2020-2039), using data collected alongside the Self-Testing AfRica Initiative. We modelled two annual distribution scenarios: (A) 1 million HIVST kits (current) or (B) up to 6.7 million kits. Incremental economic costs (2019 US$) were estimated from the provider perspective; assumptions on uptake and screening positivity were based on surveys of a subset of kit recipients and modelled using the Thembisa model. Cost-effectiveness of each distribution modality compared with the status-quo distribution configuration was estimated as cost per life year saved (estimated from life years lost due to AIDS) and optimised using a fractional factorial design. RESULTS: The largest impact resulted from secondary HIVST distribution to partners of ART patients at PHC (life years saved (LYS): 119 000 (scenario A); 393 000 (scenario B)). However, it was one of the least cost-effective modalities (A: $1394/LYS; B: $4162/LYS). Workplace distribution was cost-saving ($52-$76 million) and predicted to have a moderate epidemic impact (A: 40 000 LYS; B: 156 000 LYS). An optimised scale-up to 6.7 million tests would result in an almost threefold increase in LYS compared with a scale-up of status-quo distribution (216 000 vs 75 000 LYS). CONCLUSION: Optimisation-informed distribution has the potential to vastly improve the impact of HIVST. Using this approach, HIVST can play a key role in improving the long-term health impact of investment in HIVST.