The cyclin-dependent kinase (CDK) inhibitor p21(Cip1/Waf1) plays an essential role in the control of cell proliferation by modulating the activity of cyclin/CDK complexes in response to various intracellular or extracellular signals. Small variations in p21 expression levels may determine whether it acts as an inhibitor or an assembly factor for cyclin/CDK complexes. It is therefore critical to better characterize the mechanisms regulating p21 abundance. Here, we show, using a tetracycline-regulated system in p53-deficient DLD-1 human colon cancer cells, that p21 protein levels and stability are regulated by the proteasome-dependent degradation pathway and by association with its partners, CDKs and PCNA. A p21 mutant deficient for interaction with CDKs, p21CDK-, displayed an enhanced stability and greatly reduced sensitivity to proteasome-mediated proteolysis, indicating that association with cyclin/CDK complexes may trigger p21 degradation. In contrast, a p21 mutant impaired in the interaction with PCNA, p21PCNA-, exhibited a decreased stability, suggesting that association with PCNA protects p21 from proteasome-dependent degradation. Furthermore, the abundance of p21 itself, in addition to protein-protein interactions, may also modulate p21 stability since we found that high levels of p21 expression overcome proteasome-dependent regulation of p21 accumulation.