The EcoDam and T4Dam DNA-(adenine N6)-methyltransferases both methylate the adenine residue in GATC sites. These enzymes are highly related in amino acid sequence, but they deviate in their contact to the first base pair of the target sequence. EcoDam contacts Gua1 with K9 (which corresponds to T4Dam A6), while T4Dam contacts Gua1 with R130 (which corresponds to EcoDam Y138). We have "transplanted" the T4Dam DNA recognition into EcoDam and show that the EcoDam K9A/Y138R double mutant is highly active and specific. We also studied the intermediates of this transition: The EcoDam K9A variant showed low activity and loss of recognition of Gua1 [Horton, et al., J. Mol. Biol. 2006, 358, 559-570]. In contrast, the EcoDam Y138R variant, which carries both Gua1 recognition elements (K9 from EcoDam and R138 corresponding to R130 from T4Dam), is fully active and specific. This result indicates that a smooth evolutionary pathway exists for changing the EcoDam DNA recognition mode to T4Dam without loss of activity and without generation of evolutionary intermediates with reduced activity. We consistently observed increased activity of EcoDam variants containing Y138R; this suggests that the transition from EcoDam (Gua1 recognition through K9) to T4Dam (Gua1 recognition through R130) was driven by selective pressure towards increased catalytic activity.