N1-methylation of adenosine to m1A occurs in several different positions in tRNAs from various organisms. A methyl group at position N1 prevents Watson–Crick-type base pairing by adenosine and is therefore important for regulation of structure and stability of tRNA molecules. Thus far, only one family of genes encoding enzymes responsible for m1A methylation at position 58 has been identified, while other m1A methyltransferases (MTases) remain elusive. Here, we show that Bacillus subtilis open reading frame yqfN is necessary and sufficient for N1-adenosine methylation at position 22 of bacterial tRNA. Thus, we propose to rename YqfN as TrmK, according to the traditional nomenclature for bacterial tRNA MTases, or TrMet(m1A22) according to the nomenclature from the MODOMICS database of RNA modification enzymes. tRNAs purified from a ΔtrmK strain are a good substrate in vitro for the recombinant TrmK protein, which is sufficient for m1A methylation at position 22 as are tRNAs from Escherichia coli, which natively lacks m1A22. TrmK is conserved in Gram-positive bacteria and present in some Gram-negative bacteria, but its orthologs are apparently absent from archaea and eukaryota. Protein structure prediction indicates that the active site of TrmK does not resemble the active site of the m1A58 MTase TrmI, suggesting that these two enzymatic activities evolved independently.