Lysine deacetylases (KDACs) are enzymes that catalyze the hydrolysis of acyl groups from acyl-lysine residues. The recent identification of thousands of putative acylation sites, including specific acetylation sites, created an urgent need for biochemical methodologies aimed at better characterizing KDAC-substrate specificity and evaluating KDACs activity. To address this need, we utilized genetic code expansion technology to coexpress site-specifically acylated substrates with mammalian KDACs, and study substrate recognition and deacylase activity in live Escherichia coli. In this system the bacterial cell serves as a “biological test tube” in which the incubation of a single mammalian KDAC and a potential peptide or full-length acylated substrate transpires. We report novel deacetylation activities of Zn2+-dependent deacetylases and sirtuins in bacteria. We also measure the deacylation of propionyl-, butyryl-, and crotonyl-lysine, as well as novel deacetylation of Lys310-acetylated RelA by SIRT3, SIRT5, SIRT6, and HDAC8. This study highlights the importance of native interactions to KDAC-substrate recognition and deacylase activity.