The ubiquitination of the hypoxia-inducible factor (HIF) by the von Hippel–Lindau tumor suppressor (pVHL) plays a central role in the cellular response to changes in oxygen availability. pVHL binds to HIF only when a conserved proline in HIF is hydroxylated, a modification that is oxygen-dependent. The 1.85 angstrom structure of a 20-residue HIF-1α peptide–pVHL–ElonginB–ElonginC complex shows that HIF-1α binds to pVHL in an extended β strand–like conformation. The hydroxyproline inserts into a gap in the pVHL hydrophobic core, at a site that is a hotspot for tumorigenic mutations, with its 4-hydroxyl group recognized by buried serine and histidine residues. Although the β sheet–like interactions contribute to the stability of the complex, the hydroxyproline contacts are central to the strict specificity characteristic of signaling.