The thio-modification of tRNA that occurs in virtually all organisms affects the accuracy and efficiency of protein translation and is therefore biologically important. However, the molecular mechanism responsible for this tRNA modification in plants is largely unclear. We demonstrate here that Arabidopsis sulfurtransferase Cnx5, a ubiquitin-activating enzyme-like (UBA) protein involved in molybdopterin (MPT) biosynthesis, is strictly required for the thio-modification of cytosolic tRNAs in vivo. A previously uncharacterized ubiquitin-like (Ubl) protein Urm11 is also essential for tRNA thio-modification in Arabidopsis. When expressed in Saccharomyces cerevisiae, Cnx5 and Urm11 can substitute for the corresponding yeast orthologs ScUba4 and ScUrm1, respectively, in the thio-modification of yeast cytosolic tRNAs. However, another Ubl protein, Cnx7 of Arabidopsis, which is involved in MPT biosynthesis in conjunction with Cnx5, cannot replace yeast ScUrm1. Interestingly, the expression of a mutant form of Cnx7 in which the carboxyl-terminal six amino acids are substituted by those of Urm11 can significantly restore the thio-modification of tRNAs in the yeast urm1Δ mutant. These findings suggest that in Arabidopsis the common UBA protein Cnx5 collaborates with two functionally differentiated Ubl proteins, Urm11 and Cnx7, in the thio-modification of tRNA and MPT biosynthesis, respectively. Phylogenetic analysis revealed that although most eukaryotes contained a Cnx5-Urm11 ortholog pair and the tRNA thio-modification some fungi, including S. cerevisiae, had lost the Cnx7 ortholog and the ability to synthesize the molybdenum cofactor.