Bacterial vaginosis (BV) is a common vaginal bacterial imbalance associated with risk for HIV and poor gynecologic and obstetric outcomes. Male circumcision reduces BV-associated bacteria on the penis and decreases BV in female partners, but the link between penile microbiota and female partner BV is not well understood. We tested the hypothesis that having a female partner with BV increases BV-associated bacteria in uncircumcised men. We characterized penile microbiota composition and density (i.e., the quantity of bacteria per swab) by broad-coverage 16S rRNA gene-based sequencing and quantitative PCR (qPCR) in 165 uncircumcised men from Rakai, Uganda. Associations between penile community state types (CSTs) and female partner’s Nugent score were assessed. We found seven distinct penile CSTs of increasing density (CST1 to 7). CST1 to 3 and CST4 to 7 were the two major CST groups. CST4 to 7 had higher prevalence and abundance of BV-associated bacteria, such as Mobiluncus and Dialister, than CST1 to 3. Men with CST4 to 7 were significantly more likely to have a female partner with a high Nugent score (P = 0.03). Men with two or more extramarital partners were significantly more likely to have CST4 to 7 than men with only marital partners (CST4 to 7 prevalence ratio, 1.84; 95% confidence interval [CI], 1.16 to 2.92). Female partner Nugent BV is significantly associated with penile microbiota. Our data support the exchange of BV-associated bacteria through intercourse, which may explain BV recurrence and persistence.