The immunologically important major histocompatibility complex (MHC) harbors some of the most polymorphic genes in vertebrates. These genes presumably evolve under parasite-mediated selection and frequently show inconsistent allelic genealogies, where some alleles are more similar between species than within species. This phenomenon is thought to arise either from convergent evolution under parallel selection or from the preservation of ancient allelic lineages beyond speciation events (trans-species polymorphism, TSP). Here we examine natural populations of two sympatric stickleback species (Gasterosteus aculeatus and Pungitius pungitius) to investigate the contribution of these two mechanisms to the evolution of inconsistent allelic genealogies at the MHC. Overlapping parasite taxa between the two host species in three different habitats suggest contemporary parallel selection on the MHC genes. Accordingly, we detected a lack of species-specific phylogenetic clustering in the immunologically relevant antigen-binding residues of the MHC IIB genes which contrasted with the rest of the coding and non-coding sequence. However, clustering was not habitat-specific and a codon-usage analysis revealed patterns of similarity by descent. In this light, common descent via TSP, in combination with intra-species gene conversion, rather than convergent evolution is the more strongly supported scenario for the inconsistent genealogy at the MHC.