Increased cellular levels of oxidative stress are implicated in a large number of human diseases. Here we describe the transcription co-factor KDM5 (also known as Lid) as a new critical regulator of cellular redox state. Moreover, this occurs through a novel KDM5 activity whereby it alters the ability of the transcription factor Foxo to bind to DNA. Our microarray analyses of kdm5 mutants revealed a striking enrichment for genes required to regulate cellular levels of oxidative stress. Consistent with this, loss of kdm5 results in increased sensitivity to treatment with oxidizers, elevated levels of oxidized proteins, and increased mutation load. KDM5 activates oxidative stress resistance genes by interacting with Foxo to facilitate its recruitment to KDM5-Foxo co-regulated genes. Significantly, this occurs independently of KDM5's well-characterized demethylase activity. Instead, KDM5 interacts with the lysine deacetylase HDAC4 to promote Foxo deacetylation, which affects Foxo DNA binding.