Cyclin-dependent kinases 4 and 6 (CDK4/6) in complex with D-type cyclins promote cell cycle entry. Most human cancers contain overactive CDK4/6-cyclin D, and CDK4/6-specific inhibitors are promising anti-cancer therapeutics. Here, we investigate the critical functions of CDK4/6-cyclin D kinases, starting from an unbiased screen in the nematode Caenorhabditis elegans. We found that simultaneous mutation of lin-35, a retinoblastoma (Rb)-related gene, and fzr-1, an orthologue to the APC/C co-activator Cdh1, completely eliminates the essential requirement of CDK4/6-cyclin D (CDK-4/CYD-1) in C. elegans. CDK-4/CYD-1 phosphorylates specific residues in the LIN-35 Rb spacer domain and FZR-1 amino terminus, resembling inactivating phosphorylations of the human proteins. In human breast cancer cells, simultaneous knockdown of Rb and FZR1 synergistically bypasses cell division arrest induced by the CDK4/6-specific inhibitor PD-0332991. Our data identify FZR1 as a candidate CDK4/6-cyclin D substrate and point to an APC/C(FZR1) activity as an important determinant in response to CDK4/6-inhibitors.