The major histocompatibility complex (MHC) can be useful in guiding conservation planning because of its influence on immunity, fitness, and reproductive ecology in vertebrates. The mandrill (Mandrillus sphinx) is a threatened primate endemic to central Africa. Considerable research in this species has shown that the MHC is important for disease resistance, mate choice, and reproductive success. However, all previous MHC research in mandrills has focused on an inbred semi-captive population, so their genetic diversity may have been underestimated. Here we expand our current knowledge of mandrill MHC variation by performing next-generation sequencing of non-invasively collected fecal samples from a large wild horde in central Gabon. We observe MHC lineages and alleles shared with other primates, and we uncover 45 putative new class II MHC DRB alleles, including representatives of the DRB9 pseudogene, which has not previously been identified in mandrills. We also document methodological challenges associated with fecal samples in NGS-based MHC research. Even with high read depth, the replicability of alleles from fecal samples was lower than that of tissue samples, and allele assignments are inconsistent between sample types. Further, the common assumption that variants with very high read depth should represent true alleles does not appear to be reliable for fecal samples. Nevertheless, the use of degraded DNA in the present study still enabled significant progress in quantifying immunogenetic diversity and its evolution in wild primates.