Agonist-induced ubiquitylation and degradation of heterotrimeric guanine nucleotide-binding protein (G protein)-coupled receptors (GPCRs) play an essential role in surface receptor homeostasis, thereby tuning many physiological processes. Although beta-arrestin and affiliated E3 ligases mediate agonist-stimulated lysosomal degradation of the beta(2)-adrenergic receptor (beta(2)AR), a prototypic GPCR, the molecular cues that mark receptors for ubiquitylation and the regulation of receptor degradation by the proteasome remain poorly understood. We show that the von Hippel-Lindau tumor suppressor protein (pVHL)-E3 ligase complex, known for its regulation of hypoxia-inducible factor (HIF) proteins, interacts with and ubiquitylates the beta(2)AR, thereby decreasing receptor abundance. We further show that the interaction of pVHL with beta(2)AR is dependent on proline hydroxylation (proline-382 and -395) and that the dioxygenase EGLN3 interacts directly with the beta(2)AR to serve as an endogenous beta(2)AR prolyl hydroxylase. Under hypoxic conditions, receptor hydroxylation and subsequent ubiquitylation decrease dramatically, thus attenuating receptor degradation and down-regulation. Notably, in both cells and tissue, the abundance of endogenous beta(2)AR is shown to reflect constitutive turnover by EGLN3 and pVHL. Our findings provide insight into GPCR regulation, broaden the functional scope of prolyl hydroxylation, and expand our understanding of the cellular response to hypoxia.