Eubacterial ribosomes stalled on defective mRNAs are released through a mechanism referred to as trans-translation, depending on the coordinated actions of small protein B (SmpB) and transfer messenger RNA (tmRNA). A series of tmRNA variants with deletions in each structural domain were produced. Their structures were monitored by enzymatic and chemical probes in vitro, in the presence and absence of SmpB. Dissociation constants between these RNAs and SmpB from Aquifex aeolicus were derived by surface plasmon resonance (SPR) combined with filter binding assays. Three independent experimental evidences, including filter binding assays, SPR, and concentration titrations of the RNA–protein reactivity changes toward structural probes, indicate that the binding site that has the highest affinity for the protein is located outside the tRNA domain, upstream of the internal tag. The minimal tmRNA fragment that contains this high affinity site for SmpB, and also contains another site of lower affinity, includes the tag reading frame and three downstream pseudoknots that form a ring structure in solution.