Queuosine (Q) is a modification found at the wobble position of tRNAs with GUN anticodons. Although Q is present in most eukaryotes and bacteria, only bacteria can synthesize Q de novo. Eukaryotes acquire queuine (q), the free base of Q, from diet and/or microflora, making q an important but under-recognized micronutrient for plants, animals, and fungi. Eukaryotic type tRNA-guanine transglycosylases (eTGTs) are composed of a catalytic subunit (QTRT1) and a homologous accessory subunit (QTRTD1) forming a complex that catalyzes q insertion into target tRNAs. Phylogenetic analysis of eTGT subunits revealed a patchy distribution pattern in which gene losses occurred independently in different clades. Searches for genes co-distributing with eTGT family members identified DUF2419 as a potential Q salvage protein family. This prediction was experimentally validated in Schizosaccharomyces pombe by confirming that Q was present by analyzing tRNA(Asp) with anticodon GUC purified from wild-type cells and by showing that Q was absent from strains carrying deletions in the QTRT1 or DUF2419 encoding genes. DUF2419 proteins occur in most Eukarya with a few possible cases of horizontal gene transfer to bacteria. The universality of the DUF2419 function was confirmed by complementing the S. pombe mutant with the Zea mays (maize), human, and Sphaerobacter thermophilus homologues. The enzymatic function of this family is yet to be determined, but structural similarity with DNA glycosidases suggests a ribonucleoside hydrolase activity.