Long-term culture of mesenchymal stem cells leads to a loss of differentiation capacity, the molecular mechanism of which remains not understood. We show here that expansion of adipose stem cells (ASCs) to late passage (replicative senescence) is associated with promoter-specific and global changes in epigenetic histone modifications. In undifferentiated ASCs, inactive adipogenic and myogenic promoters are enriched in a repressive combination of trimethylated H3K4 (H3K4m3) and H3K27m3 in the absence of H3K9m3, a heterochromatin mark. Sequential chromatin immunoprecipitation assays indicate that H3K4m3 and H3K27m3 co-occupy a fraction of nucleosomes on some but not all lineage-specific promoters examined. However in cultured primary keratinocytes, adipogenic and myogenic promoters are enriched in trimethylated H3K4, K27, and K9, illustrating two distinct epigenetic states of inactive promoters related to potential for activation. H3K4m3 and H3K27m3 stably mark promoters during long-term ASC culture indicating that loss of differentiation capacity is not due to alterations in these histone modifications on these loci. Adipogenic differentiation in early passage results in H3K27 demethylation and H3K9 acetylation specifically on adipogenic promoters. On induction of differentiation in late passage, however, transcriptional upregulation is impaired, H3K27 trimethylation is maintained and H3K9 acetylation is inhibited on promoters. In addition, the polycomb proteins Ezh2 and Bmi1 are targeted to promoters. This correlates with global cellular Ezh2 increase and H3K9 deacetylation. Promoter targeting by Ezh2 and Bmi1 in late passage ASCs suggests the establishment of a polycomb-mediated epigenetic program aiming at repressing transcription.