Reprogramming of somatic cells into induced pluripotent stem cells (iPSCs) resets the epigenome to an embryonic-like state. Vitamin C enhances the reprogramming process, but the underlying mechanisms are unclear. Here we show that the histone demethylases Jhdm1a/1b are key effectors of somatic cell reprogramming downstream of vitamin C. We first observed that vitamin C induces H3K36me2/3 demethylation in mouse embryonic fibroblasts in culture and during reprogramming. We then identified Jhdm1a/1b, two known vitamin-C-dependent H3K36 demethylases, as potent regulators of reprogramming through gain- and loss-of-function approaches. Furthermore, we found that Jhdm1b accelerates cell cycle progression and suppresses cell senescence during reprogramming by repressing the Ink4/Arf locus. Jhdm1b also cooperates with Oct4 to activate the microRNA cluster 302/367, an integral component of the pluripotency machinery. Our results therefore reveal a role for H3K36me2/3 in cell fate determination and establish a link between histone demethylases and vitamin-C-induced reprogramming.