Methyltransferase (MTases) enzymes transfer methyl groups particularly on proteins and nucleotides, thereby participating in controlling the epigenetic information in both prokaryotes and eukaryotes. The concept of epigenetic regulation by DNA methylation has been extensively described for eukaryotes. However, recent studies have extended this concept to bacteria showing that DNA methylation can also exert epigenetic control on bacterial phenotypes. Indeed, the addition of epigenetic information to nucleotide sequences confers adaptive traits including virulence-related characteristics to bacterial cells. In eukaryotes, an additional layer of epigenetic regulation is obtained by post-translational modifications of histone proteins. Interestingly, in the last decades it was shown that bacterial MTases, besides playing an important role in epigenetic regulations at the microbe level by exerting an epigenetic control on their own gene expression, are also important players in host-microbe interactions. Indeed, secreted nucleomodulins, bacterial effectors that target the nucleus of infected cells, have been shown to directly modify the epigenetic landscape of the host. A subclass of nucleomodulins encodes MTase activities, targeting both host DNA and histone proteins, leading to important transcriptional changes in the host cell. In this review, we will focus on lysine and arginine MTases of bacteria and their hosts. The identification and characterization of these enzymes will help to fight bacterial pathogens as they may emerge as promising targets for the development of novel epigenetic inhibitors in both bacteria and the host cells they infect.