The ubiquitin and hypoxia-inducible factor (HIF) pathways are cellular processes involved in the regulation of a variety of cellular functions. Enzymes called ubiquitin E3 ligases perform protein ubiquitylation. The action of these enzymes can be counteracted by another group of enzymes called deubiquitinases (DUBs), which remove ubiquitin from target proteins. The balanced action of these enzymes allows cells to adapt their protein content to a variety of cellular and environmental stress factors, including hypoxia. While hypoxia appears to be a powerful regulator of the ubiquitylation process, much less is known about the impact of DUBs on the HIF system and hypoxia-regulated DUBs. Moreover, hypoxia and DUBs play crucial roles in many diseases, such as cancer. Hence, DUBs are considered to be promising targets for cancer cell-specific treatment. Here, we review the current knowledge about the role DUBs play in the control of HIFs, the regulation of DUBs by hypoxia, and their implication in cancer progression.