Aminoacyl-tRNA synthetases (aaRSs) ensure faithful translation of mRNA into protein by coupling an amino acid to a set of tRNAs with conserved anticodon sequences. Here, we show that in mitochondria of Saccharomyces cerevisiae, a single aaRS (MST1) recognizes and aminoacylates two natural tRNAs that contain anticodon loops of different size and sequence. Besides a regular tRNA(2Thr) with a threonine (Thr) anticodon, MST1 also recognizes an unusual tRNA(1Thr), which contains an enlarged anticodon loop and an anticodon triplet that reassigns the CUN codons from leucine to threonine. Our data show that MST1 recognizes the anticodon loop in both tRNAs, but employs distinct recognition mechanisms. The size but not the sequence of the anticodon loop is critical for tRNA(1Thr) recognition, whereas the anticodon sequence is essential for aminoacylation of tRNA(2Thr). The crystal structure of MST1 reveals that, while lacking the N-terminal editing domain, the enzyme closely resembles the bacterial threonyl-tRNA synthetase (ThrRS). A detailed structural comparison with Escherichia coli ThrRS, which is unable to aminoacylate tRNA(1Thr), reveals differences in the anticodon-binding domain that probably allow recognition of the distinct anticodon loops. Finally, our mutational and modeling analyses identify the structural elements in MST1 (e.g., helix α11) that define tRNA selectivity. Thus, MTS1 exemplifies that a single aaRS can recognize completely divergent anticodon loops of natural isoacceptor tRNAs and that in doing so it facilitates the reassignment of the genetic code in yeast mitochondria.