Methylation is a versatile reaction involved in the synthesis and modification of biologically active molecules, including RNAs. N6-methyl-threonylcarbamoyl adenosine (m6t6A) is a post-transcriptional modification found at position 37 of tRNAs from bacteria, insect, plants, and mammals. Here, we report that in Escherichia coli, yaeB (renamed as trmO) encodes a tRNA methyltransferase responsible for the N6-methyl group of m6t6A in tRNAThr specific for ACY codons. TrmO has a unique single-sheeted β-barrel structure and does not belong to any known classes of methyltransferases. Recombinant TrmO employs S-adenosyl-L-methionine (AdoMet) as a methyl donor to methylate t6A to form m6t6A in tRNAThr. Therefore, TrmO/YaeB represents a novel category of AdoMet-dependent methyltransferase (Class VIII). In a ΔtrmO strain, m6t6A was converted to cyclic t6A (ct6A), suggesting that t6A is a common precursor for both m6t6A and ct6A. Furthermore, N6-methylation of t6A enhanced the attenuation activity of the thr operon, suggesting that TrmO ensures efficient decoding of ACY. We also identified a human homolog, TRMO, indicating that m6t6A plays a general role in fine-tuning of decoding in organisms from bacteria to mammals.