Gut microbiota in geographically isolated host populations are often distinct. These differences have been attributed to between-population differences in host behaviors, environments, genetics, and geographic distance. However, which factors are most important remains unknown. Here we fill this gap for baboons by leveraging information on 13 environmental variables from 14 baboon populations spanning a natural hybrid zone. Sampling across a hybrid zone allowed us to additionally test whether phylosymbiosis (codiversification between hosts and their microbiota) is detectable in admixed, closely related primates. We found little evidence of genetic effects: neither host genetic ancestry, host genetic relatedness, nor genetic distance between host populations were strong predictors of baboon gut microbiota. Instead, gut microbiota were best explained by the baboons’ environments, especially the soil’s geologic history and exchangeable sodium. Indeed, soil effects were 15 times stronger than those of host-population FST, perhaps because soil predicts which foods are present, or because baboons are terrestrial and consume soil microbes incidentally with their food. Our results support an emerging picture in which environmental variation is the dominant predictor of host-associated microbiomes. We are the first to show that such effects overshadow host species identity among members of the same primate genus.