We conducted a multi-genome analysis correlating protein domain organization with the exon-intron structure of genes in nine eukaryotic genomes. We observed a significant correlation between the borders of exons and domains on a genomic scale for both invertebrates and vertebrates. In addition, we found that the more complex organisms displayed consistently stronger exon-domain correlation, with substantially more significant correlations detected in vertebrates compared with invertebrates. Our observations concur with the principles of exon shuffling theory, including the prediction of predominantly symmetric phase of introns flanking the borders of correlating exons. These results suggest that extensive exon shuffling events during evolution significantly contributed to the shaping of eukaryotic proteomes.