In Ribosome-associated Quality Control (RQC), nascent-polypeptides produced by interrupted translation are modified with C-terminal polyalanine tails ('Ala-tails') that function outside ribosomes to induce ubiquitylation by Pirh2 or CRL2-KLHDC10 E3 ligases. Here we investigate the molecular basis of Ala-tail function using biochemical and in silico approaches. We show that Pirh2 and KLHDC10 directly bind to Ala-tails, and structural predictions identify candidate Ala-tail binding sites, which we experimentally validate. The degron-binding pockets and specific pocket residues implicated in Ala-tail recognition are conserved among Pirh2 and KLHDC10 homologs, suggesting that an important function of these ligases across eukaryotes is in targeting Ala-tailed substrates. Moreover, we establish that the two Ala-tail binding pockets have convergently evolved, either from an ancient module of bacterial provenance (Pirh2) or via tinkering of a widespread C-degron recognition element (KLHDC10). These results shed light on the recognition of a simple degron sequence and the evolution of Ala-tail proteolytic signaling.