Identification of novel proteins that can potentially contribute to carcinogenesis is a requisite venture. Herein, we report the first biochemical characterization of the novel F-box and WD40 containing protein, FBXW4. We have identified interacting protein partners and demonstrated that FBXW4 is part of a ubiquitin ligase complex. Furthermore, the Fbxw4 locus is a common site of proviral insertion in a variety of retroviral insertional mutagenesis murine cancer models and Fbxw4 mRNA is highly expressed in the involuting murine mammary gland. To begin to characterize the biochemical function of Fbxw4, we used proteomic analysis to demonstrate that Fbxw4 interacts with Skp1 (SKP1), Cullin1 (CUL1), Ring-box1 (RBX1) and all components of the COP9 signalosome. All of these interactions are dependent on an intact F-box domain of Fbxw4. Furthermore, Fbxw4 is capable of interacting with ubiquitinated proteins within cells in an F-box dependent manner. Finally, we demonstrate that FBXW4 is mutated, lost and under-expressed in a variety of human cancer cell lines and clinical patient samples. Importantly, expression of FBXW4 correlates with survival of patients with non-small cell lung cancer. Taken together, we suggest that FBXW4 may be a novel tumor suppressor that regulates important cellular processes.