The universal L-shaped tertiary structure of tRNAs is maintained with the help of nucleotide modifications within the D- and T-loops, and these modifications are most extensive within hyperthermophilic species. The obligate-commensal Nanoarchaeum equitans and its phylogenetically-distinct host Ignicoccus hospitalis grow physically coupled under identical hyperthermic conditions. We report here two fundamentally different routes by which these archaea modify the key conserved nucleotide U54 within their tRNA T-loops. In N. equitans, this nucleotide is methylated by the S-adenosylmethionine-dependent enzyme NEQ053 to form m5U54, and a recombinant version of this enzyme maintains specificity for U54 in Escherichia coli. In N. equitans, m5U54 is subsequently thiolated to form m5s2U54. In contrast, I. hospitalis isomerizes U54 to pseudouridine prior to methylating its N1-position and thiolating the O4-position of the nucleobase to form the previously uncharacterized nucleotide m1s4Ψ. The methyl and thiol groups in m1s4Ψ and m5s2U are presented within the T-loop in a spatially identical manner that stabilizes the 3'-endo-anti conformation of nucleotide-54, facilitating stacking onto adjacent nucleotides and reverse-Hoogsteen pairing with nucleotide m1A58. Thus, two distinct structurally-equivalent solutions have evolved independently and convergently to maintain the tertiary fold of tRNAs under extreme hyperthermic conditions.