Deregulated centrosome duplication can result in genetic instability and contribute to tumorigenesis. Here, we show that centrosome duplication is regulated by the activity of an E3-ubiquitin ligase that employs the F-box protein FBXW5 (ref. 3) as its targeting subunit. Depletion of endogenous FBXW5 or overexpression of an F-box-deleted mutant version results in centrosome overduplication and formation of multipolar spindles. We identify the centriolar protein HsSAS-6 (refs 4,5) as a critical substrate of the SCF-FBXW5 complex. FBXW5 binds HsSAS-6 and promotes its ubiquitylation in vivo. The activity of SCF-FBXW5 is in turn negatively regulated by Polo-like kinase 4 (PLK4), which phosphorylates FBXW5 at Ser 151 to suppress its ability to ubiquitylate HsSAS-6. FBXW5 is a cell-cycle-regulated protein with expression levels peaking at the G1/S transition. We show that FBXW5 levels are controlled by the anaphase-promoting (APC/C) complex, which targets FBXW5 for degradation during mitosis and G1, thereby helping to reset the centrosome duplication machinery. In summary, we show that a cell-cycle-regulated SCF complex is regulated by the kinase PLK4, and that this in turn restricts centrosome re-duplication through degradation of the centriolar protein HsSAS-6.