The proteasome is the degradation machine at the center of the ubiquitin-proteasome system and controls the concentrations of many proteins in eukaryotes. It is highly processive so that substrates are degraded completely into small peptides, avoiding the formation of potentially toxic fragments. Nonetheless, some proteins are incompletely degraded, indicating the existence of factors that influence proteasomal processivity. We have quantified proteasomal processivity and determined the underlying rates of substrate degradation and release. We find that processivity increases with species complexity over a 5-fold range between yeast and mammalian proteasome, and the effect is due to slower but more persistent degradation by proteasomes from more complex organisms. A sequence stretch that has been implicated in causing incomplete degradation, the glycine-rich region of the NFκB subunit p105, reduces the proteasome’s ability to unfold its substrate, and polyglutamine repeats such as found in Huntington’s disease reduce the processivity of the proteasome in a length-dependent manner.