Histone modifications, including N-lysine acetylation and methylation, play critical roles in eukaryotic transcription. The addition of acetyl- and methyl-groups and removal of acetyl-groups involves redox neutral reactions, whereas demethylation is O2 dependent, a reaction with potential to enable O2 availability mediated regulation, as occurs for reactions catalysed by the 2-oxoglutarate dependent hypoxia-inducible factor (HIF) hydroxylases. A screen for substrates of the HIF-regulated Jumonji-C (JmjC) lysine demethylase KDM3A led to the finding that purified recombinant KDM3A catalyses oxidation of the N-acetyl group of Lys-9 of histone H3 giving an N-hydroxyacetyl-lysine residue. Studies employing a N-hydroxyacetyl-lysine selective antibody and mass spectrometry support the cellular relevance of N-hydroxyacetyl-lysine. The combined biochemical and cellular results reveal evidence for an unanticipated O2-mediated link between histone lysine N-acetylation and JmjC catalysis. Future work can explore the biological significance of N-hydroxyacetylation, including in the hypoxic response where KDM3A plays a role in regulating HIF target genes.