Accumulating evidence suggests that reversible protein acetylation may be a major regulatory mechanism that rivals phosphorylation. With the recent cataloging of thousands of acetylation sites on hundreds of proteins comes the challenge of identifying the acetyltransferases and deacetylases that regulate acetylation levels. Sirtuins are a conserved family of NAD(+)-dependent protein deacetylases that are implicated in genome maintenance, metabolism, cell survival, and lifespan. SIRT3 is the dominant protein deacetylase in mitochondria, and emerging evidence suggests that SIRT3 may control major pathways by deacetylation of central metabolic enzymes. Here, to identify potential SIRT3 substrates, we have developed an unbiased screening strategy that involves a novel acetyl-lysine analogue (thiotrifluoroacetyl-lysine), SPOT-peptide libraries, machine learning, and kinetic validation. SPOT peptide libraries based on known and potential mitochondrial acetyl-lysine sites were screened for SIRT3 binding and then analyzed using machine learning to establish binding trends. These trends were then applied to the mitochondrial proteome as a whole to predict binding affinity of all lysine sites within human mitochondria. Machine learning prediction of SIRT3 binding correlated with steady-state kinetic k(cat)/K(m) values for 24 acetyl-lysine peptides that possessed a broad range of predicted binding. Thus, SPOT peptide-binding screens and machine learning prediction provides an accurate and efficient method to evaluate sirtuin substrate specificity from a relatively small learning set. These analyses suggest potential SIRT3 substrates involved in several metabolic pathways such as the urea cycle, ATP synthesis, and fatty acid oxidation.