Background <p>Gut microbiota play a critical role in host health and nutrition and are regulated by both non-genetic factors such as season, diet, habitat, age, sex, and genetic variation. Although researchers studying mammalian feeding ecology have focused principally on non-genetic influences of gut microbiota composition, there is growing awareness of the important role that genes coding for the major histocompatibility complex (MHC) play in enabling the host immune system to distinguish between beneficial and pathogenic microbes.</p> Results <p>Here, we examined MHC genes <i>DRB1</i>, <i>DRB2</i>, <i>DQA1</i> and <i>DQB1</i> along with 20 neutral microsatellites to test the relationship between host genetic variation and gut microbiota in a population of wild golden snub-nosed monkeys (<i>Rhinopithecus roxellana</i>), a foregut fermenting colobine primate. In controlling for season, age, and sex, we found no significant association between gut microbiota alpha and beta diversity with overall MHC heterozygosity/diversity. However, gut microbiota composition (Weighted UniFrac distance) was significantly correlated with microsatellite diversity (<i>d</i>²). In addition, the presence/absence of MHC haplotypes was positively correlated with the relative abundance of certain core beneficial bacterial genera (i.e., <i>Anaerofustis</i> and <i>Ruminococcus</i>) and negatively correlated with the abundance of certain pathogenic bacteria (i.e., <i>Prevotellaceae genus 1 and Phascolarctobacterium</i>). Closer relatedness and higher MHC genetic similarity were independently associated with greater gut microbiota similarity.</p> Conclusions <p>Our findings support a taxon-specific association between MHC variation and gut microbiota, whereby the presence/absence of MHC haplotypes correlate with variation in particular microbial taxa rather than with global shifts in community structure.</p>