Although many African countries have achieved high levels of HIV diagnosis, funding constraints have necessitated greater focus on more efficient testing approaches. We compared the impact and cost-effectiveness of several potential new testing strategies in South Africa, and assessed the prospects of achieving the UNAIDS target of 95% of HIV-positive adults diagnosed by 2030. We developed a mathematical model to evaluate the potential impact of home-based testing, mobile testing, assisted partner notification, testing in schools and workplaces, and testing of female sex workers (FSWs), men who have sex with men (MSM), family planning clinic attenders and partners of pregnant women. In the absence of new testing strategies, the diagnosed fraction is expected to increase from 90.6% in 2020 to 93.8% by 2030. Home-based testing combined with self-testing would have the greatest impact, increasing the fraction diagnosed to 96.5% by 2030, and would be highly cost-effective compared to currently funded HIV interventions, with a cost per life year saved (LYS) of $394. Testing in FSWs and assisted partner notification would be cost-saving; the cost per LYS would also be low in the case of testing MSM ($20/LYS) and self-testing by partners of pregnant women ($130/LYS).