Post-translational modification of lysine residues via reversible acylation occurs on proteins from diverse pathways, functions, and organisms. While nuclear protein acylation reflects the competing activities of enzymatic acyltransferases and deacylases, mitochondrial acylation appears to be driven mostly via a non-enzymatic mechanism. Three protein deacylases, SIRT3, SIRT4, and SIRT5, reside in the mitochondria and remove these modifications from targeted proteins in an NAD-dependent manner. Recent proteomic surveys of mitochondrial protein acylation have identified the sites of protein acetylation, succinylation, glutarylation, and malonylation and their regulation by SIRT3 and SIRT5. Here, we review recent advances in this rapidly moving field, their biological significance, and their implications for mitochondrial function, metabolic regulation, and disease pathogenesis.