Hypoxia-inducible factor (HIF) mediates a widespread transcriptional response to hypoxia through binding to cis-acting DNA sequences termed hypoxia response elements (HREs). Activity of the transcriptional complex is suppressed in the presence of oxygen by processes that include the targeting of HIF-alpha subunits for ubiquitin-mediated proteolysis. To provide further insights into these processes we constructed Chinese hamster ovary (CHO) cells bearing stably integrated plasmids that expressed HRE-linked surface antigens and used these cells in genetic screens for mutants that demonstrated constitutive up-regulation of HRE activity. From mutagenized cultures, clones were isolated that demonstrated up-regulation of HRE activity and increased HIF-1alpha protein levels in normoxic culture. Transfection and cell fusion studies suggested that these cells possess recessive defects that affect one or more pathways involved in HIF-alpha proteolysis. Two lines were demonstrated to harbor truncating mutations in the von Hippel-Lindau (VHL) tumor suppressor gene. In these cells, defects in ubiquitylation of exogenous human HIF-1alpha in vitro could be complemented by wild type pVHL, and re-expression of a wild type VHL gene restored a normal pattern of HIF/HRE activity, demonstrating the critical dependence of HIF regulation on pVHL in CHO cells. In contrast, other mutant cells had no demonstrable mutation in the VHL gene, and ubiquitylated exogenous HIF-1alpha normally, suggesting that they contain defects at other points in the oxygen-regulated processing of HIF-alpha subunits.