F-Box proteins (FBPs) are variable adaptor proteins that earmark protein substrates for ubiquination and destruction by the proteasome. Through their N-terminal F-box motif, they couple specific protein substrates to a catalytic machinery known as SCF (Skp-1/Cul1/F-Box) E3-ubiquitin ligase. Typical FBPs bind the specific substrates in a phosphorylation dependent manner via their C-termini using either leucine rich repeats (LRR) or tryptophan-aspartic acid (WD40) domains for substrate recognition. By using a gene trap strategy that selects for genes induced during programmed cell death, we have isolated the mouse homolog of the hypothetical human F-Box protein 33 (FBX33). Here we identify FBX33 as a component of an SCF E3-ubiquitin ligase that targets the multifunctional regulator Y-box binding protein 1 (YB-1)/dbpB/p50 for polyubiquitination and destruction by the proteasome. By targeting YB-1 for proteasomal degradation, FBX33 negatively interferes with YB-1 mediated functions. In contrast to typical FBPs, FBX33 has no C-terminal LRR or WD40 domains and associates with YB-1 via its N-terminus. The present study confirms the existence of a formerly hypothetical F-Box protein in living cells and describes one of its substrates.