Guided by an in vitro selection experiment designed to obtain tight binding aptamers of Escherichia coli glutamine specific tRNA (tRNAGln) for glutaminyl-tRNA synthetase (GlnRS), we have engineered a tRNA mutant in which the five-nucleotide variable loop sequence 5'-44CAUUC48-3' is replaced by 5'-44AGGU48-3'. This mutant tRNA binds to GlnRS with 30-fold improved affinity compared to the wild type. The 2.7 A cocrystal structure of the RNA aptamer-GlnRS complex reveals major rearrangements in the central tertiary core of the tRNA, while maintaining an RNA-protein interface identical to the wild type. The repacked RNA core features a novel hydrogen bonding arrangement of the trans Levitt pair G15-U48, a new sulfate binding pocket in the major groove, and increased hydrophobic stacking interactions among the bases. These data suggest that enhanced protein binding to a mutant globular RNA can arise from stabilization of RNA tertiary interactions rather than optimization of RNA-protein contacts.