The genome of Helicobacter pylori is rich in restriction–modification (RM) systems. Approximately 4% of the genome codes for components of RM systems. hpyAVIBM, which codes for a phase-variable C5 cytosine methyltransferase (MTase) from H. pylori, lacks a cognate restriction enzyme. Over-expression of M.HpyAVIB in Escherichia coli enhances the rate of mutations. However, when the catalytically inactive F9N or C82W mutants of M.HpyAVIB were expressed in E. coli, mutations were not observed. The M.HpyAVIB gene itself was mutated to give rise to different variants of the MTase. M.HpyAVIB variants were purified and differences in kinetic properties and specificity were observed. Intriguingly, purified MTase variants showed relaxed substrate specificity. Homologues of hpyAVIBM homologues amplified and sequenced from different clinical isolates showed similar variations in sequence. Thus, hpyAVIBM presents an interesting example of allelic variations in H. pylori where changes in the nucleotide sequence result in proteins with new properties.