The positively charged lysine residue plays an important role in protein folding and functions. Neutralization of the charge often has a profound impact on the substrate proteins. Accordingly all the known post-translational modifications at lysine have pivotal roles in cell physiology and pathology. Here we report the discovery of two novel, in vivo lysine modifications in histones, lysine propionylation and butyrylation. We confirmed, by in vitro labeling and peptide mapping by mass spectrometry, that two previously known acetyltransferases, p300 and CREB-binding protein, could catalyze lysine propionylation and lysine butyrylation in histones. Finally p300 and CREB-binding protein could carry out autopropionylation and autobutyrylation in vitro. Taken together, our results conclusively establish that lysine propionylation and lysine butyrylation are novel post-translational modifications. Given the unique roles of propionyl-CoA and butyryl-CoA in energy metabolism and the significant structural changes induced by the modifications, the two modifications are likely to have important but distinct functions in the regulation of biological processes.