Protein post-translational modifications (PTMs) at the lysine residue, such as lysine methylation, acetylation, and ubiquitination, are diverse, abundant, and dynamic. They play a key role in the regulation of diverse cellular physiology. Here we report discovery of a new type of lysine PTM, lysine malonylation (Kmal). Kmal was initially detected by mass spectrometry and protein sequence-database searching. The modification was comprehensively validated by Western blot, tandem MS, and high-performance liquid chromatography of synthetic peptides, isotopic labeling, and identification of multiple Kmal substrate proteins. Kmal is a dynamic and evolutionarily conserved PTM observed in mammalian cells and bacterial cells. In addition, we demonstrate that Sirt5, a member of the class III lysine deacetylases, can catalyze lysine demalonylation and lysine desuccinylation reactions both in vitro and in vivo. This result suggests the possibility of nondeacetylation activity of other class III lysine deacetylases, especially those without obvious acetylation protein substrates. Our results therefore reveal a new type of PTM pathway and identify the first enzyme that can regulate lysine malonylation and lysine succinylation status.