Selective protein degradation targeted by members of the F-box protein family plays pivotal roles in cell biology. It is widely accepted that an F-box protein directs substrate ubiquitination within a Skp1⋅CUL1⋅F-box protein⋅ROC1 (SCF-ROC1) E3 ubiquitin ligase complex. This assembly utilizes the CUL1 molecular scaffold, allowing the F-box protein to position its bound substrate for ubiquitination by a ROC1-recruited E2-conjugating enzyme. Here, we describe an alternative mechanism for assembling an F-box protein-based E3 complex through a previously uncharacterized cullin, CUL7, identified by mass spectrometry as a ROC1-interacting protein. CUL7 is a large polypeptide containing a cullin domain, which is responsible for ROC1 binding, and a DOC domain, which is also present in the anaphase-promoting complex. Remarkably, CUL7 assembles an SCF-ROC1-like E3 ubiquitin ligase complex consisting of Skp1, CUL7, the Fbx29 F-box protein, and ROC1. In contrast to CUL1 that binds Skp1 by itself, CUL7 interacts with the Skp1⋅Fbx29 complex, but not with Skp1 alone. Strikingly, CUL7 selectively interacts with Skp1⋅Fbx29 but not with Skp1⋅βTRCP2 or Skp1⋅Skp2. Thus, CUL7 may define a previously uncharacterized, Fbx29-mediated, and ubiquitin-dependent proteolysis pathway.