Aging is linked to loss of the self-renewal capacity of adult stem cells. Here, we observed that human multipotent stem cells (MSCs) underwent cellular senescence in vitro. Decreased expression of histone deacetylases (HDACs), followed by downregulation of polycomb group genes (PcGs), such as BMI1, EZH2 and SUZ12, and by upregulation of jumonji domain containing 3 (JMJD3), was observed in senescent MSCs. Similarly, HDAC inhibitors induced cellular senescence through downregulation of PcGs and upregulation of JMJD3. Regulation of PcGs was associated with HDAC inhibitor-induced hypophosphorylation of RB, which causes RB to bind to and decrease the transcriptional activity of E2F. JMJD3 expression regulation was dependant on histone acetylation status at its promoter regions. A histone acetyltransferase (HAT) inhibitor prevented replicative senescence of MSCs. These results suggest that HDAC activity might be important for MSC self-renewal by balancing PcGs and JMJD3 expression, which govern cellular senescence by p16(INK4A) regulation.