Antiretroviral-based strategies for HIV prevention have shown inconsistent results in women. We investigated whether vaginal microbiota modulated tenofovir gel microbicide efficacy in the CAPRISA (Centre for the AIDS Program of Research in South Africa) 004 trial. Two major vaginal bacterial community types—one dominated by Lactobacillus (59.2%) and the other where Gardnerella vaginalis predominated with other anaerobic bacteria (40.8%)—were identified in 688 women profiled. Tenofovir reduced HIV incidence by 61% (P = 0.013) in Lactobacillus-dominant women but only 18% (P = 0.644) in women with non-Lactobacillus bacteria, a threefold difference in efficacy. Detectible mucosal tenofovir was lower in non-Lactobacillus women, negatively correlating with G. vaginalis and other anaerobic bacteria, which depleted tenofovir by metabolism more rapidly than target cells convert to pharmacologically active drug. This study provides evidence linking vaginal bacteria to microbicide efficacy through tenofovir depletion via bacterial metabolism.