Generally, F-box proteins are the substrate recognition subunits of SCF (Skp1–Cul1–F-box protein) ubiquitin ligase complexes, which mediate the timely proteolysis of important eukaryotic regulatory proteins^,. Mammalian genomes encode roughly 70 F-box proteins, but only a handful have established functions^,. The F-box protein family obtained its name from Cyclin F (also called Fbxo1), in which the F-box motif (the ∼40-amino-acid domain required for binding to Skp1) was first described. Cyclin F, which is encoded by an essential gene, also contains a cyclin box domain, but in contrast to most cyclins, it does not bind or activate any cyclin-dependent kinases (CDKs)^,,. However, like other cyclins, Cyclin F oscillates during the cell cycle, with protein levels peaking in G2. Despite its essential nature and status as the founding member of the F-box protein family, Cyclin F remains an orphan protein, whose functions are unknown. Starting from an unbiased screen, we identified CP110, a protein that is essential for centrosome duplication, as an interactor and substrate of Cyclin F. Using a mode of substrate binding distinct from other F-box protein–substrate pairs, CP110 and Cyclin F physically associate on the centrioles during the G2 phase of the cell cycle, and CP110 is ubiquitylated by the SCF^{Cyclin F} ubiquitin ligase complex, leading to its degradation. siRNA-mediated depletion of Cyclin F in G2 induces centrosomal and mitotic abnormalities, such as multipolar spindles and asymmetric, bipolar spindles with lagging chromosomes. These phenotypes were reverted by co-silencing CP110 and were recapitulated by expressing a stable mutant of CP110 that cannot bind Cyclin F. Finally, expression of a stable CP110 mutant in cultured cells also promotes the formation of micronuclei, a hallmark of chromosome instability. We propose that SCF^{Cyclin F}-mediated degradation of CP110 is required for the fidelity of mitosis and genome integrity.