The F-box protein Fbxw7 (also known as Fbw7, SEL-10, hCdc4 or hAgo) mediates the ubiquitylation and thereby contributes to the degradation of proteins that positively regulate cell cycle. Conditional ablation of Fbxw7 in mouse embryonic fibroblasts (MEFs) induces cell-cycle arrest accompanied by abnormal accumulation of the intracellular domain of Notch1 (NICD1) and c-Myc. However, the molecular mechanisms by which the accumulation of NICD1 and c-Myc induces cell-cycle arrest have remained unclear. We have now examined the expression of cell-cycle inhibitors in Fbxw7-deficient MEFs and found that the abundance of p27(Kip1) and p57(Kip2) is paradoxically decreased. This phenomenon appears to be attributable to the accumulation of NICD1, given that it was recapitulated by overexpression of NICD1 and blocked by ablation of RBP-J. Conversely, the expression of p16(Ink4a) and p19(ARF) was increased in an NICD1-independent manner in Fbxw7-null MEFs. The increased expression of p19(ARF) was recapitulated by overexpression of c-Myc and abolished by ablation of c-Myc, suggesting that the accumulation of c-Myc is primarily responsible for that of p19(ARF). In contrast, the upregulation of p16(Ink4a) appeared to be independent of c-Myc. These results indicate that cell-cycle inhibitors undergo complex regulation by the Fbxw7-mediated proteolytic system.