Lysine acetylation is a post-translational modification that is reversed by lysine deacetylases (KDACs). The goal of this work was to identify determinants of substrate specificity for KDACs, focusing on short-range interactions occurring with residues immediately following the acetyllysine. Using a fluorescence-based in vitro assay, we determined the activity for each enzyme with a limited panel of derivative substrate peptides, revealing a distinct reactivity profile for each enzyme. We mapped the interaction surface for KDAC6, KDAC8, and KDAC1 with the +1 and +2 substrate residues (with respect to acetyllysine) based on enzyme-substrate interaction pairs observed in molecular dynamics simulations. Characteristic residues in each KDAC interact preferentially with particular substrate residues and correlate with either enhanced or inhibited activity. Although nonpolar aromatic residues generally enhanced activity with all KDACs, the manner in which each enzyme interacted with these residues is distinct. Furthermore, each KDAC has distinctive interactions that correlate with lower activity, primarily ionic in nature. KDAC8 exhibited the most diverse and widest range of effects, while KDAC6 was sensitive only to the +1 position and KDAC1 selectivity was primarily driven by negative selection. The substrate preferences were validated for KDAC6 and KDAC8 using a set of peptides derived from known acetylated proteins. Overall, we determined how KDAC6, KDAC8, and KDAC1 achieve substrate specificity with residues following the acetyllysine. These new insights into KDAC specificity will be critical for identifying novel substrates of particular KDACs, designing KDAC-specific inhibitors, and demonstrate a general framework for understanding substrate specificity for other enzyme classes.