Hypoxia is not only a developmental cue but also a stress and pathological stimulus in many human diseases. The response to hypoxia at the cellular level relies on the activity of the transcription factor hypoxia inducible factor (HIF) family. HIF-1 is responsible for the acute response and transactivates a variety of genes involved in cellular metabolism, cell death and cell growth. Here we show that hypoxia results in increased mRNA levels for human KDM2 family members, KDM2A and KDM2B, and also Drosophila melanogaster kdm2, a histone and protein demethylase. In human cells, KDM2 family member’s mRNA levels are regulated by HIF-1 but not HIF-2 in hypoxia. Interestingly, only KDM2A protein levels are significantly induced in a HIF-1 dependent manner, while KDM2B protein changes in a cell type dependent manner. Importantly, we demonstrate that in human cells, KDM2A regulation by hypoxia and HIF-1 occurs at the level of promoter, with HIF 1 binding to the KDM2A promoter being required for RNA polymerase II recruitment. Taken together these results demonstrate that KDM2 is a novel HIF target that can help coordinate the cellular response to hypoxia. In addition, these results might explain why KDM2 levels are often deregulated in human cancers.