Histone modifications, including Nε-lysine acetylation and methylation, play critical roles in the regulation of eukaryotic transcription. The addition of acetyl and methyl groups and removal of acetyl groups to histones involve redox-neutral reactions. Demethylation is O2-dependent, as reported for reactions catalysed by the 2-oxoglutarate-dependent hypoxia-inducible factor (HIF) hydroxylases, one of which is structurally related to the Jumonji-C (JmjC) histone demethylases. We screened for substrates of the HIF-regulated JmjC lysine demethylase KDM3A and unexpectedly observed that purified recombinant KDM3A catalyses oxidation of the Nε-acetyl group of the Lys-9 of histone H3 (H3K9ac) giving an Nε-hydroxyacetylated product (H3K9acOH). Here we show that Nε-hydroxyacetyl-lysine is recognized by proteins known to bind to H3K9ac, including histone deacetylases and the YEATS domain-containing AF9. Studies employing an Nε-hydroxyacetyl-lysine selective antibody and mass spectrometry support the cellular relevance of Nε-hydroxyacetyl-lysine. Our combined biochemical and cellular results provide evidence for an unanticipated O2-mediated link between histone lysine Nε-acetylation and JmjC catalysis.