The molecular mechanism responsible for a decline of stem cell functioning after replicative stress remains unknown. We used mouse embryonic fibroblasts (MEFs) and hematopoietic stem cells (HSCs) to identify genes involved in the process of cellular aging. In proliferating and senescent MEFs one of the most differentially expressed transcripts was Enhancer of zeste homolog 2 (Ezh2), a Polycomb group protein (PcG) involved in histone methylation and deacetylation. Retroviral overexpression of Ezh2 in MEFs resulted in bypassing of the senescence program. More importantly, whereas normal HSCs were rapidly exhausted after serial transplantations, overexpression of Ezh2 completely conserved long-term repopulating potential. Animals that were reconstituted with 3 times serially transplanted control bone marrow cells all died due to hematopoietic failure. In contrast, similarly transplanted Ezh2-overexpressing stem cells restored stem cell quality to normal levels. In a “genetic genomics” screen, we identified novel putative Ezh2 target or partner stem cell genes that are associated with chromatin modification. Our data suggest that stabilization of the chromatin structure preserves HSC potential after replicative stress.