BACKGROUND: Sociodemographic, behavioral and clinical correlates of the vaginal microbiome (VMB) as characterized by molecular methods have not been adequately studied. VMB dominated by bacteria other than lactobacilli may cause inflammation, which may facilitate HIV acquisition and other adverse reproductive health outcomes. METHODS: We characterized the VMB of women in Kenya, Rwanda, South Africa and Tanzania (KRST) using a 16S rDNA phylogenetic microarray. Cytokines were quantified in cervicovaginal lavages. Potential sociodemographic, behavioral, and clinical correlates were also evaluated. RESULTS: Three hundred thirteen samples from 230 women were available for analysis. Five VMB clusters were identified: one cluster each dominated by Lactobacillus crispatus (KRST-I) and L. iners (KRST-II), and three clusters not dominated by a single species but containing multiple (facultative) anaerobes (KRST-III/IV/V). Women in clusters KRST-I and II had lower mean concentrations of interleukin (IL)-1α (p < 0.001) and Granulocyte Colony Stimulating Factor (G-CSF) (p = 0.01), but higher concentrations of interferon-γ-induced protein (IP-10) (p < 0.01) than women in clusters KRST-III/IV/V. A lower proportion of women in cluster KRST-I tested positive for bacterial sexually transmitted infections (STIs; ptrend = 0.07) and urinary tract infection (UTI; p = 0.06), and a higher proportion of women in clusters KRST-I and II had vaginal candidiasis (ptrend = 0.09), but these associations did not reach statistical significance. Women who reported unusual vaginal discharge were more likely to belong to clusters KRST-III/IV/V (p = 0.05). CONCLUSION: Vaginal dysbiosis in African women was significantly associated with vaginal inflammation; the associations with increased prevalence of STIs and UTI, and decreased prevalence of vaginal candidiasis, should be confirmed in larger studies.