Transcriptional dysregulation, which can be caused by genetic and epigenetic alterations, is a fundamental feature of many cancers. A key cytoprotective transcriptional activator, NRF2, is often aberrantly activated in non-small cell lung cancers (NSCLCs) and supports both aggressive tumorigenesis and therapeutic resistance. Herein, we find that persistently activated NRF2 in NSCLCs generates enhancers at gene loci that are not normally regulated by transiently activated NRF2 under physiological conditions. Elevated accumulation of CEBPB in NRF2-activated NSCLCs is found to be one of the prerequisites for establishment of the unique NRF2-dependent enhancers, among which the NOTCH3 enhancer is shown to be critical for promotion of tumor-initiating activity. Enhancer remodeling mediated by NRF2-CEBPB cooperativity promotes tumor-initiating activity and drives malignancy of NRF2-activated NSCLCs via establishment of the NRF2-NOTCH3 regulatory axis.