Oxygen-dependent proteolytic destruction of hypoxia-inducible factor-alpha (HIF-alpha) subunits plays a central role in regulating transcriptional responses to hypoxia. Recent studies have defined a key function for the von Hippel-Lindau tumour suppressor E3 ubiquitin ligase (VHLE3) in this process, and have defined an interaction with HIF-1 alpha that is regulated by prolyl hydroxylation. Here we show that two independent regions within the HIF-alpha oxygen-dependent degradation domain (ODDD) are targeted for ubiquitylation by VHLE3 in a manner dependent upon prolyl hydroxylation. In a series of in vitro and in vivo assays, we demonstrate the independent and non-redundant operation of each site in regulation of the HIF system. Both sites contain a common core motif, but differ both in overall sequence and in the conditions under which they bind to the VHLE3 ligase complex. The definition of two independent destruction domains implicates a more complex system of pVHL-HIF-alpha interactions, but reinforces the role of prolyl hydroxylation as an oxygen-dependent destruction signal.