The von Hippel-Lindau tumor suppressor protein (pVHL) has emerged as a key factor in cellular responses to oxygen availability, being required for the oxygen-dependent proteolysis of alpha subunits of hypoxia inducible factor-1 (HIF). Mutations in VHL cause a hereditary cancer syndrome associated with dysregulated angiogenesis, and up-regulation of hypoxia inducible genes. Here we investigate the mechanisms underlying these processes and show that extracts from VHL-deficient renal carcinoma cells have a defect in HIF-alpha ubiquitylation activity which is complemented by exogenous pVHL. This defect was specific for HIF-alpha among a range of substrates tested. Furthermore, HIF-alpha subunits were the only pVHL-associated proteasomal substrates identified by comparison of metabolically labeled anti-pVHL immunoprecipitates from proteosomally inhibited cells and normal cells. Analysis of pVHL/HIF-alpha interactions defined short sequences of conserved residues within the internal transactivation domains of HIF-alpha molecules sufficient for recognition by pVHL. In contrast, while full-length pVHL and the p19 variant interact with HIF-alpha, the association was abrogated by further N-terminal and C-terminal truncations. The interaction was also disrupted by tumor-associated mutations in the beta-domain of pVHL and loss of interaction was associated with defective HIF-alpha ubiquitylation and regulation, defining a mechanism by which these mutations generate a constitutively hypoxic pattern of gene expression promoting angiogenesis. The findings indicate that pVHL regulates HIF-alpha proteolysis by acting as the recognition component of a ubiquitin ligase complex, and support a model in which its beta domain interacts with short recognition sequences in HIF-alpha subunits.