The enzyme tRNA-guanine transglycosylase (TGT) is involved in the queuosine modification of tRNAs in eukarya and eubacteria and in the archaeosine modification of tRNAs in archaea. However, the different classes of TGTs utilize different heterocyclic substrates (and tRNA in the case of archaea). Based on the X-ray structural analyses, an earlier study [Stengl et al. (2005) Mechanism and substrate specificity of tRNA-guanine transglycosylases (TGTs): tRNA-modifying enzymes from the three different kingdoms of life share a common catalytic mechanism. Chembiochem, 6, 1926-1939] has made a compelling case for the divergent evolution of the eubacterial and archaeal TGTs. The X-ray structure of the eukaryal class of TGTs is not known. We performed sequence homology and phylogenetic analyses, and carried out enzyme kinetics studies with the wild-type and mutant TGTs from Escherichia coli and human using various heterocyclic substrates that we synthesized. Observations with the Cys145Val (E. coli) and the corresponding Val161Cys (human) TGTs are consistent with the idea that the Cys145 evolved in eubacterial TGTs to recognize preQ(1) but not queuine, whereas the eukaryal equivalent, Val161, evolved for increased recognition of queuine and a concomitantly decreased recognition of preQ(1). Both the phylogenetic and kinetic analyses support the conclusion that all TGTs have divergently evolved to specifically recognize their cognate heterocyclic substrates.