Dysregulated behavior of cell cycle proteins and their control by ubiquitin E3 ligases is an emerging theme in human lung cancer. Here, we identified and characterized the activity of a novel F-box protein, termed FBXL2, belonging to the SCF (Skip-Cullin1-F-box protein) E3 ligase family. Ectopically expressed FBXL2 triggered G2/M-phase arrest, induced chromosomal anomalies and increased apoptosis of transformed lung epithelia by mediating polyubiquitination and degradation of the mitotic regulator, cyclin D3. Unlike other F-box proteins that target phosphodegrons within substrates, FBXL2 uniquely recognizes a canonical calmodulin (CaM)-binding motif within cyclin D3 to facilitate its polyubiquitination. CaM bound and protected cyclin D3 from FBXL2 by direct intermolecular competition with the F-box protein for access within this motif. The chemotherapeutic agent vinorelbine increased apoptosis of human lung carcinoma cells by inducing FBXL2 expression and cyclin D3 degradation, an effect accentuated by CaM knockdown. Depletion of endogenous FBXL2 stabilized cyclin D3 levels, accelerated cancer cell growth and increased cell viability after vinorelbine treatment. Last, ectopic expression of FBXL2 significantly inhibited the growth and migration of tumorogenic cells and tumor formation in athymic nude mice. These observations implicate SCF FBXL2 as an indispensible regulator of mitosis that serves as a tumor suppressor.