O-GlcNAcylation is an essential, nutrient-sensitive post-translational modification, but its biochemical and phenotypic effects remain incompletely understood. To address this question, we investigated the global transcriptional response to perturbations in O-GlcNAcylation. Unexpectedly, many transcriptional effects of O-GlcNAc transferase (OGT) inhibition were due to the activation of NRF2, the master regulator of redox stress tolerance. Moreover, we found that a signature of low OGT activity strongly correlates with NRF2 activation in multiple tumor expression datasets. Guided by this information, we identified KEAP1 (also known as KLHL19), the primary negative regulator of NRF2, as a direct substrate of OGT. We show that O-GlcNAcylation of KEAP1 at serine 104 is required for the efficient ubiquitination and degradation of NRF2. Interestingly, O-GlcNAc levels and NRF2 activation co-vary in response to glucose fluctuations, indicating that KEAP1 O-GlcNAcylation links nutrient sensing to downstream stress resistance. Our results reveal a novel regulatory connection between nutrient-sensitive glycosylation and NRF2 signaling and provide a blueprint for future approaches to discover functionally important O-GlcNAcylation events on other KLHL family proteins in various experimental and disease contexts.