The cyclin-dependent kinase (CDK) inhibitor p27 is degraded at the G 0-G1 transition of the cell cycle by the ubiquitin-proteasome pathway in a Skp2-independent manner. We recently identified a novel ubiquitin ligase, KPC (Kip1 ubiquitylation-promoting complex), consisting of KPC1 and KPC2, which regulates the ubiquitin-dependent degradation of p27 at G1 phase. We have now investigated the structural requirements for the interactions of KPC1 with KPC2 and p27. The NH2-terminal region of KPC1 was found to be responsible for binding to KPC2 and to p27. KPC1 mutants that lack this region failed to mediate polyubiquitylation of p27 in vitro and expression of one such mutant delayed p27 degradation in vivo. We also generated a series of deletion mutants of p27 and found that KPC failed to polyubiquitylate a p27 mutant that lacks the CDK inhibitory domain. Interestingly, the cyclin E-CDK2 complex prevented both the interaction of KPC with p27 as well as KPC-mediated polyubiquitylation of p27. A complex of cyclin E with a kinase-negative mutant of CDK2 also exhibited these inhibitory effects, suggesting that cyclin E-CDK2 competes with KPC1 for access to the CDK inhibitory domain of p27. These results suggest that free p27 is recognized by the NH2-terminal region of KPC1, which also associates with KPC2, and that p27 is then polyubiquitylated by the COOH-terminal RING-finger domain of KPC1.