The SCF (Skp1/cullin-1/F-box protein) class of E3 polyubiquitin ligases generates a signal for proteasomal degradation of thousands of proteins in animals. The evolutionary diversification of the F-box protein (FBP) family of substrate receptor subunits has challenged elucidation of these complexes in protists. Using bioinformatics and orthogonal Skp1 interactome methods, we expand the list of putative FBPs in the social amoeba Dictyostelium and show that Skp1 interactions are highly remodeled between growth and development. In addition, a subset of FBPs was less represented when the posttranslational hydroxylation and glycosylation of the Skp1 subunit was abrogated by deletion of the O2-dependent Skp1 prolyl hydroxylase PhyA. The significance of Skp1 modification for SCF activity was indicated by partial rescue of phyA-KO cell development with proteasomal inhibitors.