The F-box protein Skp2 mediates c-Myc ubiquitylation by binding to the MB2 domain. However, the turnover of c-Myc is largely dependent on phosphorylation of threonine-58 and serine-62 in MB1, residues that are often mutated in cancer. We now show that the F-box protein Fbw7 interacts with and thereby destabilizes c-Myc in a manner dependent on phosphorylation of MB1. Whereas wild-type Fbw7 promoted c-Myc turnover in cells, an Fbw7 mutant lacking the F-box domain delayed it. Furthermore, depletion of Fbw7 by RNA interference increased both the abundance and transactivation activity of c-Myc. Accumulation of c-Myc was also apparent in mouse Fbw7-/- embryonic stem cells. These observations suggest that two F-box proteins, Fbw7 and Skp2, differentially regulate c-Myc stability by targeting MB1 and MB2, respectively.