Although regulation of histone methylation is believed to contribute to embryonic stem cell (ESC) self-renewal, the mechanisms remain obscure. We show here that the histone H3 trimethyl lysine 4 (H3K4me3) demethylase, KDM5B, is a downstream Nanog target and critical for ESC self-renewal. Although KDM5B is believed to function as a promoter-bound repressor, we find that it paradoxically functions as an activator of a gene network associated with self-renewal. ChIP-Seq reveals that KDM5B is predominantly targeted to intragenic regions and that it is recruited to H3K36me3 via an interaction with the chromodomain protein MRG15. Depletion of KDM5B or MRG15 increases intragenic H3K4me3, increases cryptic intragenic transcription, and inhibits transcriptional elongation of KDM5B target genes. We propose that KDM5B activates self-renewal-associated gene expression by repressing cryptic initiation and maintaining an H3K4me3 gradient important for productive transcriptional elongation.