Background: Tenofovir gel, an antiretroviral-based vaginal microbicide, reduced HIV acquisition by 39% in women in a recent randomized controlled clinical trial in South Africa. Methods: To inform policy, we used a dynamical model of HIV transmission, calibrated to the epidemic in South Africa, to determine the population-level impact of this microbicide on HIV incidence, prevalence, and deaths and to evaluate its cost-effectiveness. Results: If women use tenofovir gel in 80% or more of sexual encounters (high coverage), it could avert 2.33 (0.12 to 4.63) million new infections and save 1.30 (0.07 to 2.42) million lives and if used in 25% of sexual encounters (low coverage), it could avert 0.50 (0.04 to 0.77) million new infections and save 0.29 (0.02 to 0.44) million deaths, over the next 20 years. At US $0.50 per application, the cost per infection averted at low coverage is US $2392 (US $562 to US $4222) and the cost per disability-adjusted life year saved is US $104 (US $27 to US $181); at high coverage the costs are about 30% less. Conclusions: Over 20 years, the use of tenofovir gel in South Africa could avert up to 2 million new infections and 1 million AIDS deaths. Even with low rates of gel use, it is highly cost-effective and compares favorably with other control methods. This female-controlled prevention method could have a significant impact on the epidemic of HIV in South Africa. Programs should aim to achieve gel use in more than 25% of sexual encounters to significantly alter the course of the epidemic.