Cholera toxin travels from the plasma membrane to the endoplasmic reticulum of host cells, where a portion of the toxin, the A1-chain, is unfolded and targeted to a protein-conducting channel for retrotranslocation to the cytosol. Unlike most retrotranslocation substrates, the A1-chain escapes degradation by the proteasome and refolds in the cytosol to induce disease. How this occurs remains poorly understood. Here, we show that an unstructured peptide appended to the N terminus of the A1-chain renders the toxin functionally inactive. Cleavage of the peptide extension prior to cell entry rescues toxin half-life and function. The loss of toxicity is explained by rapid degradation by the proteasome after retrotranslocation to the cytosol. Degradation of the mutant toxin does not follow the N-end rule but depends on the two Lys residues at positions 4 and 17 of the native A1-chain, consistent with polyubiquitination at these sites. Thus, retrotranslocation and refolding of the wild-type A1-chain must proceed in a way that protects these Lys residues from attack by E3 ligases.