During trans-translation, transfer-messenger RNA (tmRNA) and small protein B (SmpB), together rescue ribosomes stalled on a truncated mRNA, and tag the nascent polypeptide for degradation. We used electron cryo-microscopy to determine structures of three key states of the tmRNA-SmpB-ribosome complex during trans-translation at 3.7-4.4 Å resolutions. The results show how tmRNA and SmpB act specifically on stalled ribosomes and how the circularized complex moves through the ribosome enabling translation to switch from the old defective message to the reading frame on tmRNA.