Propionylation has been identified recently as a new type of protein post-translational modification. Bacterial propionyl-CoA synthetase and human histone H4 are propionylated at specific lysine residues that have been known previously to be acetylated. However, other proteins subject to this modification remain to be identified, and the modifying enzymes involved need to be characterized. In this work, we report the discovery of histone H3 propionylation in mammalian cells. Propionylation at H3 lysine Lys(23) was detected in the leukemia cell line U937 by mass spectrometry and Western analysis using a specific antibody. In this cell line, the propionylated form of Lys(23) accounted for 7%, a level at least 6-fold higher than in other leukemia cell lines (HL-60 and THP-1) or non-leukemia cell lines (HeLa and IMR-90). The propionylation level in U937 cells decreased remarkably during monocytic differentiation, indicating that this modification is dynamically regulated. Moreover, in vitro assays demonstrated that histone acetyltransferase p300 can catalyze H3 Lys(23) propionylation, whereas histone deacetylase Sir2 can remove this modification in the presence of NAD(+). These results suggest that histone propionylation might be generated by the same set of enzymes as for histone acetylation and that selection of donor molecules (propionyl-CoA versus acetyl-CoA) may determine the difference of modifications. Because like acetyl-CoA, propionyl-CoA is an important intermediate in biosynthesis and energy production, histone H3 Lys(23) propionylation may provide a novel epigenetic regulatory mark for cell metabolism.