The histone H3 demethylase Not dead yet-1 (Ndy1/KDM2B) is a physiological inhibitor of senescence. Here, we show that Ndy1 is down-regulated during senescence in mouse embryonic fibroblasts (MEFs) and that it represses the Ink4a/Arf locus. Ndy1 counteracts the senescence-associated down-regulation of Ezh2, a component of polycomb-repressive complex (PRC) 2, via a JmjC domain-dependent process leading to the global and Ink4a/Arf locus-specific up-regulation of histone H3K27 trimethylation. The latter promotes the Ink4a/Arf locus-specific binding of Bmi1, a component of PRC1. Ndy1, which interacts with Ezh2, also binds the Ink4a/Arf locus and demethylates the locus-associated histone H3K36me2 and histone H3K4me3. The combination of histone modifications driven by Ndy1 interferes with the binding of RNA Polymerase II, resulting in the transcriptional silencing of the Ink4a/Arf locus and contributing to the Ndy1 immortalization phenotype. Other studies show that, in addition to inhibiting replicative senescence, Ndy1 inhibits Ras oncogene-induced senescence via a similar molecular mechanism.