The cellular response to hypoxia is regulated through enzymatic oxygen sensors, including the prolyl hydroxylases, which control degradation of the well-known hypoxia inducible factors (HIFs). Other enzymatic oxygen sensors have been recently identified, including members of the KDM histone demethylase family. Little is known about how different oxygen-sensing pathways interact and if this varies depending on the form of hypoxia, such as chronic or intermittent. In this study, we investigated how two proposed cellular oxygen-sensing systems, HIF-1 and KDM4A, KDM4B, and KDM4C, respond in cells exposed to rapid forms of intermittent hypoxia (minutes) and compared to chronic hypoxia (hours). We found that intermittent hypoxia increases HIF-1α protein through a pathway distinct from chronic hypoxia, involving the KDM4A, KDM4B, and KDM4C histone lysine demethylases. Intermittent hypoxia increases the quantity and activity of KDM4A, KDM4B, and KDM4C, resulting in a decrease in histone 3 lysine 9 (H3K9) trimethylation near the HIF1A locus. We demonstrate that this contrasts with chronic hypoxia, which decreases KDM4A, KDM4B, and KDM4C activity, leading to hypertrimethylation of H3K9 globally and at the HIF1A locus. Altogether, we found that demethylation of histones bound to the HIF1A gene in intermittent hypoxia increases HIF1A mRNA expression, which has the downstream effect of increasing overall HIF-1 activity and expression of HIF target genes. This study highlights how multiple oxygen-sensing pathways can interact to regulate and fine tune the cellular hypoxic response depending on the period and length of hypoxia.