The degenerate base at position 34 of the tRNA anticodon is the target of numerous modification enzymes. In Saccharomyces cerevisiae, five tRNAs exhibit a complex modification of uridine 34 (mcm(5)U(34) and mcm(5)s(2)U(34)), the formation of which requires at least 25 different proteins. The addition of the last methyl group is catalyzed by the methyltransferase Trm9p. Trm9p interacts with Trm112p, a 15-kDa protein with a zinc finger domain. Trm112p is essential for the activity of Trm11p, another tRNA methyltransferase, and for Mtq2p, an enzyme that methylates the translation termination factor eRF1/Sup45. Here, we report that Trm112p is required in vivo for the formation of mcm(5)U(34) and mcm(5)s(2)U(34). When produced in Escherichia coli, Trm112p forms a complex with Trm9p, which renders the latter soluble. This recombinant complex catalyzes the formation of mcm(5)U(34) on tRNA in vitro but not mcm(5)s(2)U(34). An mtq2-0 trm9-0 strain exhibits a synthetic growth defect, thus revealing the existence of an unexpected link between tRNA anticodon modification and termination of translation. Trm112p is associated with other partners involved in ribosome biogenesis and chromatin remodeling, suggesting that it has additional roles in the cell.