Bacterial communities colonizing the reproductive tracts of primates (including humans) impact the health, survival and fitness of the host, and thereby the evolution of the host species. Despite their importance, we currently have a poor understanding of primate microbiomes. The composition and structure of microbial communities vary considerably depending on the host and environmental factors. We conducted comparative analyses of the primate vaginal microbiome using pyrosequencing of the 16S rRNA genes of a phylogenetically broad range of primates to test for factors affecting the diversity of primate vaginal ecosystems. The nine primate species included: humans (Homo sapiens), yellow baboons (Papio cynocephalus), olive baboons (Papio anubis), lemurs (Propithecus diadema), howler monkeys (Alouatta pigra), red colobus (Piliocolobus rufomitratus), vervets (Chlorocebus aethiops), mangabeys (Cercocebus atys) and chimpanzees (Pan troglodytes). Our results indicated that all primates exhibited host-specific vaginal microbiota and that humans were distinct from other primates in both microbiome composition and diversity. In contrast to the gut microbiome, the vaginal microbiome showed limited congruence with host phylogeny, and neither captivity nor diet elicited substantial effects on the vaginal microbiomes of primates. Permutational multivariate analysis of variance and Wilcoxon tests revealed correlations among vaginal microbiota and host species-specific socioecological factors, particularly related to sexuality, including: female promiscuity, baculum length, gestation time, mating group size and neonatal birth weight. The proportion of unclassified taxa observed in nonhuman primate samples increased with phylogenetic distance from humans, indicative of the existence of previously unrecognized microbial taxa. These findings contribute to our understanding of host-microbe variation and coevolution, microbial biogeography, and disease risk, and have important implications for the use of animal models in studies of human sexual and reproductive diseases.