Two DNA methyltransferases, Dam and β-class cell cycle-regulated DNA methyltransferase (CcrM), are key mediators of bacterial epigenetics. CcrM from the bacterium Caulobacter crescentus (CcrM C. crescentus, methylates adenine at 5'-GANTC-3') displays 105-107-fold sequence discrimination against noncognate sequences. However, the underlying recognition mechanism is unclear. Here, CcrM C. crescentus activity was either improved or mildly attenuated with substrates having one to three mismatched bp within or adjacent to the recognition site, but only if the strand undergoing methylation is left unchanged. By comparison, single-mismatched substrates resulted in up to 106-fold losses of activity with α (Dam) and γ-class (M.HhaI) DNA methyltransferases. We found that CcrM C. crescentus has a greatly expanded DNA-interaction surface, covering six nucleotides on the 5' side and eight nucleotides on the 3' side of its recognition site. Such a large interface may contribute to the enzyme's high sequence fidelity. CcrM C. crescentus displayed the same sequence discrimination with single-stranded substrates, and a surprisingly large (>107-fold) discrimination against ssRNA was largely due to the presence of two or more riboses within the cognate (DNA) site but not outside the site. Results from C-terminal truncations and point mutants supported our hypothesis that the recently identified C-terminal, 80-residue segment is essential for dsDNA recognition but is not required for single-stranded substrates. CcrM orthologs from Agrobacterium tumefaciens and Brucella abortus share some of these newly discovered features of the C. crescentus enzyme, suggesting that the recognition mechanism is conserved. In summary, CcrM C. crescentus uses a previously unknown DNA recognition mechanism.