Responding appropriately to changes in oxygen availability is essential for multicellular organism survival. Molecularly, cells have evolved intricate gene expression programmes to handle this stressful condition. Although it is appreciated that gene expression is co-ordinated by changes in transcription and translation in hypoxia, much less is known about how chromatin changes allow for transcription to take place. The missing link between co-ordinating chromatin structure and the hypoxia-induced transcriptional programme could be in the form of a class of dioxygenases called JmjC (Jumonji C) enzymes, the majority of which are histone demethylases. In the present review, we will focus on the function of JmjC histone demethylases, and how these could act as oxygen sensors for chromatin in hypoxia. The current knowledge concerning the role of JmjC histone demethylases in the process of organism development and human disease will also be reviewed.