Histone deacylases are erasers of Nε-acyl-lysine post-translational modifications and have been targeted for decades for the treatment of cancer, neurodegeneration and other disorders. Due to their relatively promiscuous activity on peptide substrates in vitro, it has been challenging to determine the individual targets and substrate identification mechanisms of each isozyme, and they have been considered redundant regulators. In recent years, biochemical and biophysical studies have incorporated the use of reconstituted nucleosomes, which has revealed a diverse and complex arsenal of recognition mechanisms by which histone deacylases may differentiate themselves in vivo. In this review, we first present the peptide-based tools that have helped characterize histone deacylases in vitro to date, and we discuss the new insights that nucleosome tools are providing into their recognition of histone substrates within chromatin. Then, we summarize the powerful semi-synthetic approaches that are moving forward the study of chromatin-associated factors, both in vitro by detailed single-molecule mechanistic studies, and in cells by live chromatin modification. We finally offer our perspective on how these new techniques would advance the study of histone deacylases. We envision that such studies will help elucidate the role of individual isozymes in disease and provide a platform for the development of the next generation of therapeutics.