The great polymorphism observed in the major histocompatibility complex (MHC) genes is thought to be maintained by pathogen-mediated selection possibly combined with MHC-disassortative mating, guided by MHC-determined olfactory cues. Here, we partly characterize the MHC class I and II B of the blue petrel, Halobaena caerulea (Procellariiformes), a bird with significant olfactory abilities that lives under presumably low pathogen burdens in Subantarctica. Blue petrels are long-lived, monogamous birds which suggest the necessity of an accurate mate choice process. The species is ancestral to songbirds (Passeriformes; many MHC loci), although not to gamefowls (Galliformes; few MHC loci). Considering the phylogenetic relationships and the low subantarctic pathogen burden, we expected few rather than many MHC loci in the blue petrel. However, when we analysed partial MHC class I and class II B cDNA and gDNA sequences we found evidence for as many as at least eight MHC class I loci and at least two class II B loci. These class I and II B sequences showed classical MHC characteristics, e.g. high nucleotide diversity, especially in putative peptide-binding regions where signatures of positive selection was detected. Trans-species polymorphism was found between MHC class II B sequences of the blue petrel and those of thin-billed prion, Pachyptila belcheri, two species that diverged similar to 25 MYA. The observed MHC allele richness in the blue petrel may well serve as a basis for mate choice, especially since olfactory discrimination of MHC types may be possible in this species.