A key enzyme involved in the incorporation of the modified base queuine into tRNA (position 34) is tRNA-guanine transglycosylase (TGT). Studies of the recognition of truncated tRNAs by the Escherichia coli TGT have established a minimal recognition motif involving a minihelix with a 7 base loop containing a U-G-U sequence (where G is replaced with queuine) [Curnow, A.W. and Garcia, G.A. (1995) J. Biol. Chem. 270, 17264-17267; Nakanishi, S. et al. (1994) J. Biol. Chem. 269, 32221-32225]. Still, a clearer understanding of the recognition of full-length 'queuine-cognate' tRNAs by TGT remains lacking. In this paper, we report the in vitro transcription and enzymological characterization (Km, and kcat) of all four 'queuine-cognate' tRNAs from E. coli and from Saccharomyces cerevisiae with the TGT from E. coli. No primary or secondary structures emerge as important recognition elements from this study. The modest differences in substrate specificity (relative kcat/Km values vary from 0.5 to 8.4) seen among these 'queuine-cognate' tRNAs most likely result from the accumulated effects of many subtle factors. Interestingly, the yeast tRNAs are essentially equivalent to the E. coli tRNAs as substrates for TGT, indicating that there is nothing intrinsic to the yeast tRNAs that accounts for the absence of queuine in yeast.