FEM1A, FEM1B, and FEM1C are evolutionarily-conserved VHL-box proteins, the substrate recognition subunits of CUL2-RING E3 ubiquitin ligase complexes. Here, we report that FEM1 proteins are ancient regulators of Stem-Loop Binding Protein (SLBP), a conserved protein that interacts with the stem loop structure located in the 3′ end of canonical histone mRNAs and functions in mRNA cleavage, translation and degradation. SLBP levels are highest during S-phase coinciding with histone synthesis. The ubiquitin ligase complex SCF cyclin F targets SLBP for degradation in G2 phase; however, the regulation of SLBP during other stages of the cell cycle is poorly understood. We provide evidence that FEM1A, FEM1B, and FEM1C interact with and mediate the degradation of SLBP. Cyclin F, FEM1A, FEM1B and FEM1C all interact with a region in SLBP's N-terminus using distinct degrons. An SLBP mutant that is unable to interact with all four ligases is expressed at higher levels than wild type SLBP and does not oscillate during the cell cycle. We demonstrate that orthologues of SLBP and FEM1 proteins interact in C. elegans and D. melanogaster , suggesting that the pathway is evolutionarily conserved. Furthermore, we show that FEM1 depletion in C. elegans results in the upregulation of SLBP orthologue CDL-1 in oocytes. Notably, cyclin F is absent in flies and worms, suggesting that FEM1 proteins play an important role in SLBP targeting in lower eukaryotes.