Skp1 is a subunit of E3SCFUbiquitin-ligases and other protein complexes (1). In the social soil amoeba Dictyostelium discoideum, Skp1 contains a novel hydroxyproline (Hyp)1-linked pentasaccharide. The Hyp-glycosylation pathway consists of P4H1, a non-heme Fe(II)-dependent dioxygenase that modifies Skp1 at Pro143, and five sequentially acting cytoplasmic glycosyltransferase activities encoded by three genes (2). P4H1 may serve as an O2 sensor, as the enzyme has a high Km for O2 in vitro (3), elevated O2 levels are required for P4H1-null cells to culminate into fruiting bodies, and reduced O2 is sufficient for P4H1-overexpression cells (4). Reverse genetic analyses suggest that the sequential post-translational glycosylation events modulate the effect of hydroxylation in hierarchical fashion (5). Based on biochemical and genetic studies, Skp1 is the only substrate for P4H1 and the glycosyltransferases in cells, and mediates the role of the pathway enzymes on culmination and other developmental transitions (6). As recently summarized (2), the Hyp-glycosylation pathway appears to be widely expressed in unicellular protists including some significant human and plant pathogens. Among known prolyl 4-hydroxylases, P4H1 is most related to the sequences of Egl-9 (Eggless-9), an enzyme involved in O2-regulation in C. elegans, and the 3 human homologs that sense O2 in humans. Egl-9 and the human PHDs (prolyl hydroxylase domain proteins; also known as EGLNs or HPHs) modify hypoxia-inducible factor-α (HIFα), a subunit of the HIFα-HIF® transcriptional factor heterodimer whose accumulation directly induces hypoxia response genes that support glycolysis, angiogenesis, and erythropoiesis (7). Hydroxylation of Pro402 or Pro564 of HIFα results in recognition by the von Hippel-Lindau subunit of the E3VBCUb-ligase followed by degradation within the 26S-proteasome. Egl-9 and human PHD1-3 are thought to serve as direct O2-sensors, in part due to their relatively high Km values for O2 as a substrate. Their activity in cells is promoted by the availability of the co-substrate αKG (α-ketoglutarate, a Krebs cycle intermediate), ascorbate, and Fe(II), and inhibited by the product succinate, other Krebs cycle metabolites, and reactive oxygen species (e.g., 8,9). Much remains to be learned about the regulation of PHDs, and the significance of additional PHD targets in animal cells (10). Whereas HIFα and possibly other proteins mediate PHD/Egl-9-dependent hypoxic responses in animal cells, Dictyostelium apparently lacks HIFα and the VBC-complex that recognizes it, and P4H1-dependent hypoxic responses appear to be mediated by Skp1 (6). Conversely, though Skp1 is highly conserved in eukaryotes, the equivalent of Pro143 is notably absent in chordates. Interestingly, Skp1 is evolutionarily related, not to HIFα, but to elongin C, a subunit of the E3VBCUb-ligase that targets HIFα for degradation. The homologous E3SCFUb ligases, conserved from yeast to humans, contain the SCF subcomplex whose Skp1 adaptor links the scaffold protein cullin-1 to an F-box protein, which presents targets such as cell cycle and other regulatory proteins for polyubiquitination. Analysis of the human and Dictyostelium genomes predicts more than 50 F-box proteins (unpublished data), potentially diversifying the pool of SCF complexes, and thereby suggesting a global role in regulation of the proteome (11). Interestingly, there is no evidence that P4H1 regulates the stability of its Skp1 target (6). A biochemical analysis of substrate selection by P4H1 was initiated to provide insight into mechanism of this evolutionary shift between protists and animals, and to reveal clues about regulation of its hydroxylase activity. As shown here, adoption of a direct P4H1 assay revealed similar sensitivity to metabolic inhibitors, and 1H-NMR studies demonstrated formation of (2S,4R)-4-hydroxy-L-proline (a.k.a. trans-4-hydroxyproline, Hyp), as for human PHD2 (12–14). However, whereas PHD2 recognizes truncated oxygen-dependent degradation domains (ODDs) of HIFα, and peptides as short as 15-mers have successfully been employed as substrates, P4H1-processing of Skp1 depended on global structural attributes. Remarkably, substrate recognition is conserved in animal Skp1s. The implication that P4H1 recognition depends on conserved features important for SCF-complex formation was supported by loss of substrate activity when Skp1 was complexed with an F-box protein. Such a recognition mechanism could explain P4H1’s apparent high degree of specificity for Skp1, and suggests how Skp1 modification may be regulated in cells. A similar dependence on Skp1 features was observed for the Hyp-capping activity of Gnt1, whose gene is phylogenetically co-distributed with protist P4H1 and in some genomes appears to be encoded as a separate domain of the same protein (2). Whereas animal PHD’s render global effects by regulating the half-life of HIFα with transcriptional consequences on many genes, global effects of Dictyostelium P4H1 and its partner Gnt1 may be rendered by the targeting of Skp1 alone that controls the half-lives of many proteins via the large family of E3SCFUb-ligases.