Cells use redox signaling to adapt to oxidative stress. For instance, certain transcription factors exist in a latent state that may be disrupted by oxidative modifications that activate their transcription potential. We hypothesized that DNA-binding sites (response elements) for redox-sensitive transcription factors may also exist in a latent state, maintained by co-repressor complexes containing class I histone deacetylase (HDAC) enzymes, and that HDAC inactivation by oxidative stress may antagonize deacetylase activity and unmask electrophile-response elements, thus activating transcription. Electrophiles suitable to test this hypothesis include reactive carbonyl species, often derived from peroxidation of arachidonic acid. We report that alpha,beta-unsaturated carbonyl compounds, e.g. the cyclopentenone prostaglandin, 15-deoxy-Delta12,14-PGJ(2) (15d-PGJ(2)), and 4-hydroxy-2-nonenal (4HNE), alkylate (carbonylate), a subset of class I HDACs including HDAC1, -2, and -3, but not HDAC8. Covalent modification at two conserved cysteine residues, corresponding to Cys(261) and Cys(273) in HDAC1, coincided with attenuation of histone deacetylase activity, changes in histone H3 and H4 acetylation patterns, derepression of a LEF1.beta-catenin model system, and transcription of HDAC-repressed genes, e.g. heme oxygenase-1 (HO-1), Gadd45, and HSP70. Identification of particular class I HDACs as components of the redox/electrophile-responsive proteome offers a basis for understanding how cells stratify their responses to varying degrees of pathophysiological oxidative stress associated with inflammation, cancer, and metabolic syndrome.