The protein substrates of sirtuin 5-regulated lysine malonylation (Kmal) remain unknown, hindering its functional analysis. In this study, we carried out proteomic screening, which identified 4042 Kmal sites on 1426 proteins in mouse liver and 4943 Kmal sites on 1822 proteins in human fibroblasts. Increased malonyl-CoA levels in malonyl-CoA decarboxylase (MCD)-deficient cells induces Kmal levels in substrate proteins. We identified 461 Kmal sites showing more than a 2-fold increase in response to MCD deficiency as well as 1452 Kmal sites detected only in MCD−/− fibroblast but not MCD+/+ cells, suggesting a pathogenic role of Kmal in MCD deficiency. Cells with increased lysine malonylation displayed impaired mitochondrial function and fatty acid oxidation, suggesting that lysine malonylation plays a role in pathophysiology of malonic aciduria. Our study establishes an association between Kmal and a genetic disease and offers a rich resource for elucidating the contribution of the Kmal pathway and malonyl-CoA to cellular physiology and human diseases.