The hypoxia inducible factor (HIF) pathway and the ubiquitin system represent major cellular processes that are involved in the regulation of a plethora of cellular signaling pathways and tissue functions. The ubiquitin system controls the ubiquitination of proteins, which is the covalent linkage of one or several ubiquitin molecules to specific targets. This ubiquitination is catalyzed by approximately 1000 different E3 ubiquitin ligases and can lead to different effects, depending on the type of internal ubiquitin chain linkage. The best-studied function is the targeting of proteins for proteasomal degradation. The activity of E3 ligases is antagonized by proteins called deubiquitinases (or deubiquitinating enzymes), which negatively regulate ubiquitin chains. This is performed in most cases by the catalytic removal of these chains from the targeted protein. The HIF pathway is regulated in an oxygen-dependent manner by oxygen-sensing hydroxylases. Covalent modification of HIFα subunits leads to the recruitment of an E3 ligase complex via the von Hippel-Lindau (VHL) protein and the subsequent polyubiquitination and proteasomal degradation of HIFα subunits, demonstrating the regulation of the HIF pathway by the ubiquitin system. This unidirectional effect of an E3 ligase on the HIF pathway is the best-studied example for the interplay between these two important cellular processes. However, additional regulatory mechanisms of the HIF pathway through the ubiquitin system are emerging and, more recently, also the reciprocal regulation of the ubiquitin system through components of the HIF pathway. Understanding these mechanisms and their relevance for the activity of each other is of major importance for the comprehensive elucidation of the oxygen-dependent regulation of cellular processes. This review describes the current knowledge of the functional bidirectional interplay between the HIF pathway and the ubiquitin system on the protein level.