The standard genetic code is used by most living organisms, yet deviations have been observed in many genomes, suggesting that the genetic code has been evolving. In certain yeast mitochondria, CUN codons are reassigned from leucine to threonine, which requires an unusual tRNA(Thr) with an enlarged 8-nt anticodon loop ( ). To trace its evolutionary origin we performed a comprehensive phylogenetic analysis which revealed that evolved from yeast mitochondrial tRNA(His). To understand this tRNA identity change, we performed mutational and biochemical experiments. We show that Saccharomyces cerevisiae mitochondrial threonyl-tRNA synthetase (MST1) could attach threonine to both and the regular , but not to the wild-type tRNA(His). A loss of the first nucleotide (G(-1)) in tRNA(His) converts it to a substrate for MST1 with a K(m) value (0.7 μM) comparable to that of (0.3 μM), and addition of G(-1) to allows efficient histidylation by histidyl-tRNA synthetase. We also show that MST1 from Candida albicans, a yeast in which CUN codons remain assigned to leucine, could not threonylate , suggesting that MST1 has coevolved with . Our work provides the first clear example of a recent recoding event caused by alloacceptor tRNA gene recruitment.