Transfer RNA (tRNA) is structurally unique among nucleic acids in harboring an astonishing diversity of post-transcriptionally modified nucleoside. Two of the most radically modified nucleosides known to occur in tRNA are queuosine and archaeosine, both of which are characterized by a 7-deazaguanosine core structure. In spite of the phylogenetic segregation observed for these nucleosides (queuosine is present in Eukarya and Bacteria, while archaeosine is present only in Archaea), their structural similarity suggested a common biosynthetic origin, and recent biochemical and genetic studies have provided compelling evidence that a significant portion of their biosynthesis may in fact be identical. This review covers current understanding of the physiology and biosynthesis of these remarkable nucleosides, with particular emphasis on the only two enzymes that have been discovered in the pathways: tRNA-guanine transglycosylase (TGT), which catalyzes the insertion of a modified base into the polynucleotide with the concomitant elimination of the genetically encoded guanine in the biosynthesis of both nucleosides, and S-adenosylmethionine:tRNA ribosyltransferase-isomerase (QueA), which catalyzes the penultimate step in the biosynthesis of queuosine, the construction of the carbocyclic side chain.