Studies of MHC-based mate choice in wild populations generally test hypotheses by assuming female choice and male-male competition, whether or not mate choice dynamics have been previously determined for the species under study. Here we examined mate choice patterns in a small burrow-nesting seabird, the Leach’s storm-petrel (Oceanodroma leucorhoa), using the Major Histocompatibility Complex (MHC). The life history and ecology of this species is extreme: both partners work together to fledge a single chick during the breeding season, a task that requires regularly traveling hundreds of kilometers to and from foraging grounds over a six to eight-week provisioning period. Using a five-year dataset unprecedented for this species (n=1027 adults and 925 chicks), we found a positive relationship between variation in female reproductive quality and heterozygosity at Ocle-DAB2, a MHC class IIB locus. Contrary to previous reports rejecting disassortative mating as a mechanism for maintaining genetic polymorphism in this species, here we show that males make significant disassortative mate choice decisions. Variability in female reproductive success suggests that the most common homozygous females (Ocle-DAB201 / Ocle-DAB201) may be physiologically disadvantaged and, therefore, less preferred as lifelong partners for choosy males. The results from this study support the role of mate choice in maintaining high levels of MHC variability in a wild seabird species, and highlights the need to incorporate a broader ecological framework and sufficient sample sizes into studies of MHC-based mating patterns in wild populations in general.