Engineering the specificity of DNA-modifying enzymes has proven extremely challenging, as sequence recognition by these enzymes is poorly understood. Here we used directed evolution to generate a variant of HaeIII methyltransferase that efficiently methylates a novel target site. M.HaeIII methylates the internal cytosine of the canonical sequence GGCC, but there is promiscuous methylation of a variety of non-canonical sites, notably AGCC, at a reduced rate. Using in vitro compartmentalization (IVC), libraries of M.HaeIII genes were selected for the ability to efficiently methylate AGCC. A two-step mutagenesis strategy, involving initial randomization of DNA-contacting residues followed by randomization of the loop that lies behind these residues, yielded a mutant with a 670-fold improvement in catalytic efficiency (k(cat)/K(m)(DNA)) using AGCC and a preference for AGCC over GGCC. The mutant methylates three sites efficiently (AGCC, CGCC and GGCC). Indeed, it methylates CGCC slightly more efficiently than AGCC. However, the mutant discriminates against other non-canonical sites, including TGCC, as effectively as the wild-type enzyme. This study provides a rare example of a laboratory-evolved enzyme whose catalytic efficiency surpasses that of the wild-type enzyme with the principal substrate.