To understand the evolutionary process of the DNA mismatch repair system, we conducted systematic phylogenetic analysis of its key components, the bacterial MutS and MutL genes and their eukaryotic homologs. Based on genome-wide homolog searches, we identified three new MutS subfamilies (MutS3-5) in addition to the previously studied MutS1 and MutS2 subfamilies. Detailed evolutionary analysis strongly suggests that frequent ancient horizontal gene transfer (HGT) occurred with both MutS and MutL genes from bacteria to eukaryotes and/or archaea. Our results further imply that the origins of mismatch repair system in eukaryotes and archaea are largely attributed to ancient HGT from bacteria instead of vertical evolution. Specifically, the eukaryotic MutS and MutL homologs likely originated from endosymbiotic ancestors of mitochondria or chloroplasts, indicating that not only archaea, but also bacteria are important sources of eukaryotic DNA metabolic genes. The archaeal MutS1 and MutL homologs were also acquired from bacteria simultaneously through HGT. Moreover, the distribution and evolution profiles of the MutS1 and MutL genes suggest that they have undergone long-term coevolution. Our work presents an overall portrait of the evolution of these important genes in DNA metabolism and also provides further understanding about the early evolution of cellular organisms.