Systematic testing for Vibrio cholerae O1 is rare, which means that the world's limited supply of oral cholera vaccines (OCVs) may not be delivered to areas with the highest true cholera burden. Here we used a phenomenological model with subnational geographic targeting and fine-scale vaccine effects to model how expanding V. cholerae testing affected impact and cost-effectiveness for preventive vaccination campaigns across different bacteriological confirmation and vaccine targeting assumptions in 35 African countries. Systematic testing followed by OCV targeting based on confirmed cholera yielded higher efficiency and cost-effectiveness and slightly fewer averted cases than status quo scenarios targeting suspected cholera. Targeting vaccine to populations with an annual incidence rate greater than 10 per 10,000, the testing scenario averted 10.8 (95% prediction interval (PI) 9.4-12.6) cases per 1,000 fully vaccinated persons while the status quo scenario averted 6.9 (95% PI 6.0-7.8) cases per 1,000 fully vaccinated persons. In the testing scenario, testing costs increased by US$31 (95% PI 25-39) while vaccination costs reduced by US$248 (95% PI 176-326) per averted case compared to the status quo. Introduction of systematic testing into cholera surveillance could improve efficiency and reach of global OCV supply for preventive vaccination.