Ribosome-associated quality control (RQC) is a conserved process degrading potentially toxic truncated nascent peptides whose malfunction underlies neurodegeneration and proteostasis decline in aging. During RQC, dissociation of stalled ribosomes is followed by elongation of the nascent peptide with alanine and threonine residues, driven by Rqc2 independently of mRNA, the small ribosomal subunit and guanosine triphosphate (GTP)-hydrolyzing factors. The resulting CAT tails (carboxy-terminal tails) and ubiquitination by Ltn1 mark nascent peptides for proteasomal degradation. Here we present ten cryogenic electron microscopy (cryo-EM) structures, revealing the mechanistic basis of individual steps of the CAT tailing cycle covering initiation, decoding, peptidyl transfer, and tRNA translocation. We discovered eIF5A as a crucial eukaryotic RQC factor enabling peptidyl transfer. Moreover, we observed dynamic behavior of RQC factors and tRNAs allowing for processivity of the CAT tailing cycle without additional energy input. Together, these results elucidate key differences as well as common principles between CAT tailing and canonical translation.