DNA N4-cytosine methyltransferases (N4mC MTases) are a family of S-adenosyl-L-methionine (AdoMet)-dependent MTases. Members of this family were previously found to share nine conserved sequence motifs, but the evolutionary basis of these similarities has never been studied in detail. We performed phylogenetic analysis of 37 known and potential new family members from the multiple sequence alignment using distance matrix, parsimony and maximum likelihood approaches to infer the evolutionary relationship among the N4mC MTases and classify them into groups of orthologs. All the treeing algorithms employed as well as results of exhaustive sequence database searching support a scenario, in which the majority of N4mC MTases, except for M. Bal I and M. Bam HI, arose by divergence from a common ancestor. Interestingly, MTases M. Bal I and M. Bam HI apparently originated from N6-adenine MTases and represent the most recent addendum to the N4mC MTase family. In addition to the previously reported nine sequence motifs, two more conserved sequence patches were detected. Phylogenetic analysis also provided the evidence for massive horizontal transfer of MTase genes, presumably with the whole restriction-modification systems, between Bacteria and Archaea.