Background: The vaginal microbiome is an important site of bacterial-mammalian symbiosis. This symbiosis is currently best characterized for humans, where lactobacilli dominate the microbial community and may help defend women against infectious disease. However, lactobacilli do not dominate the vaginal microbiota of any other mammal studied to date, raising key questions about the forces that shape the vaginal microbiome in non-human mammals. Results: We used Illumina sequencing of the bacterial 16S rRNA gene to investigate variation in the taxonomic composition of the vaginal microbiota in 48 baboons (Papio cynocephalus), members of a well-studied wild population in Kenya. Similar to prior studies, we found that the baboon vaginal microbiota was not dominated by lactobacilli. Despite this difference, and similar to humans, reproductive state was the dominant predictor of baboon vaginal microbiota, with pregnancy, postpartum amenorrhea, and ovarian cycling explaining 18% of the variance in community composition. Furthermore, among cycling females, a striking 39% of variance in community composition was explained by ovarian cycle phase, with an especially distinctive microbial community around ovulation. Peri-ovulatory females exhibited the highest relative abundance of lactic acid-producing bacteria compared to any other phase, with a mean relative abundance of 44%. To a lesser extent, sexual behavior, especially a history of shared sexual partners, also predicted vaginal microbial similarity between baboons. Conclusions: Despite striking differences in their dominant microbes, both human and baboon vaginal microbiota exhibit profound changes in composition in response to reproductive state, ovarian cycle phase, and sexual behavior. We found major shifts in composition during ovulation, which may have implications for disease risk and conception success. These findings highlight the need for future studies to account for fine-scale differences in reproductive state, particularly differences between the various phases of the ovarian cycle. Overall, our work contributes to an emerging understanding of the forces that explain intra- and inter-individual variation in the mammalian vaginal microbiome, with particular emphasis on its role in host health and disease risk.