The cell-cycle regulator p21^Cip1 is degraded by proteasomes independently of ubiquitination. We now show that degradation of p21 in vivo does not require the 19S proteasome lid, which contains the ubiquitin-binding subunit. Instead, the major proteasomal pathway for p21 degradation involves an alternative proteasome lid, the REGγ complex. REGγ binds to p21 in vivo, and deletion of p21's REGγ-binding site greatly extends its half-life. Knockdown of REGγ by RNA interference stabilizes p21, p21 has a significantly extended half-life in REGγ^−/− murine embryonic fibroblasts, and the p21 abundance is elevated in REGγ^−/− mice. The role of REGγ in cell-cycle regulation may extend beyond p21 regulation, because p16^INK4A and p19^Arf also bind to REGγ and are stabilized in REGγ-deficient cells.