In the present in vitro selection study, we isolated and characterized RNA aptamers for a tRNA-binding protein (Trbp) from an extremophile archaeon Aeropyrum pernix. Trbp-like structures are frequently found not only in aminoacyl-tRNA synthetases but also in diverse types of proteins from different organisms. They likely arose early in evolution and have played important roles in evolution through interactions with key RNA structures. RNA aptamers specific for A. pernix Trbp were successfully selected from a pool of RNAs composed of 60 nucleotides, including a random 30-nucleotide region. From the secondary structures, we obtained a shortened sequence composed of 21 nucleotides, of which the 3′-terminal single stranded CA nucleotides are essential for binding. This may be related to the initial evolutionary role of the universal CCA-3′ terminus of tRNA in the interaction with Trbp-like structures.