In this article, we describe how we reconstructed a precise, minimal proto-MHC region in the ancestor of euchordates, which was based on a comparison of the MHC-paralogy group of vertebrate with the MHC-like chromosome of cephalochordates. This deduced ancestral region was compared with the genomes of extant species, other deuterostomes and protostomes. Our analysis revealed statistically significant traces of conservation in these species, suggesting that a proto-MHC region existed at the origin of all bilaterian species. We also propose a new approach to reconstruct ancestral genomes, which combines both stringent statistical testing and phylogenetic analysis.