Post-translational modification of histone proteins are known to play an important role in regulating chromatin structure. In an effort to find additional histone modifications we set out to screen enzymes of the 2-oxoglutarate and Fe(II)-dependent (2-OG-Fe(II)) dioxygenase family for activity towards histones. Here we show that the Schizosaccharomyces pombe 2-OG-Fe(II) dioxygenase domain containing protein-2 (Ofd2) is a histone H2A dioxygenase enzyme. Using a combination of peptide screening and alanine scanning substitution analysis, we identify an HxxLR motif in H2A as a substrate for Ofd2 activity. Transcriptional profiling indicates that Ofd2 regulates the repression of oxidative phosphorylation genes during hypoxic stress. We show that Ofd2 is recruited to the 5′ end of oxidative phosphorylation genes specifically during hypoxia and that it uses its dioxygenase activity to regulate their transcription. Together, these data uncover a novel histone H2A modifying activity involved in the regulation of gene expression during hypoxia.