We determined the predictive accuracy of penile bacteria for incident BV in female sex partners. In this prospective cohort, we enrolled Kenyan men aged 18-35 and their female sex partners aged 16 and older. We assessed BV at baseline, 1, 6, and 12 months. Incident BV was defined as a Nugent score of 7-10 at a follow-up visit, following a Nugent score of 0-6 at baseline. Amplification of the V3-V4 region of the bacterial 16S rRNA gene was performed on meatal and glans/coronal sulcus swab samples. Majority vote classifier combined the decisions of three machine learning classification algorithms (Random Forest, Support Vector Machine, K Nearest Neighbor). We report the estimate cross-validation predictive accuracy for incident BV based on baseline penile taxa. The incidence of BV was 31% among 168 couples in which the woman did not have BV at baseline: 37.3% if the man was uncircumcised vs. 26.3% if the man was circumcised. Incident BV occurred at 1 month ( = 23), 6 months ( = 20), 12 months ( = 9). The predictive capacity of meatal taxa was high: sensitivity (80.7%), specificity (74.6%), accuracy (77.5%), area under the curve (88.8%). Variable importance ranking identified meatal taxa that in the vagina are associated with BV: , and were among the top 10 most predictive taxa. The accuracy of glans/coronal sulcus taxa to predict incident BV was comparable to meatal taxa accuracy, but with greater variability. Baseline penile microbiota accurately predicted BV incidence in women who did not have BV at baseline, with more than half of incident infections observed at 6- to 12- months after penile microbiome assessment. These results suggest interventions to manipulate the penile microbiome may reduce BV incidence in sex partners, and that potential treatment (antibiotic or live biotherapeutic) will need to be effective in reducing or altering bacteria at both the glans/coronal sulcus and urethral sites (as represented by the meatus). The temporal association clarifies that concordance of penile microbiome with the vaginal microbiome of sex partners is not merely reflecting the vaginal microbiome, but can contribute to it.