Sirtuins, a group of NAD+-dependent deacylases, have emerged as the key connection between NAD+ metabolism and aging. This class of enzymes hydrolyzes a range of ε-N-acyllysine PTMs, and determining the repertoire of catalyzed deacylation reactions is of high importance to fully elucidate the roles of a given sirtuin. Here we have identified and produced two potential sirtuins from the probiotic bacterium Lactobacillus acidophilus NCFM. Screening more than 80 different substrates, covering 26 acyl groups on five peptide scaffolds, demonstrated that one of the investigated proteins, Sir2La, is a bona fide NAD+-dependent sirtuin, catalyzing hydrolysis of acetyl-, propionyl-, and butyryllysine. Further substantiating the identity of Sir2La as a sirtuin, known sirtuin inhibitors, nicotinamide and suramin, as well as a thioacetyllysine compound inhibit the deacylase activity in a concentration-dependent manner. On the basis of steady-state kinetics, Sir2La showed a slight preference for propionyllysine (Kpro) over acetyllysine (Kac). For nonfluorogenic peptide substrates, the preference is driven by a remarkably low KM (280 nM vs 700 nM, for Kpro and Kac, respectively), whereas kcat was similar (21 × 10–3 s–1). Moreover, while NAD+ is a prerequisite for Sir2La-mediated deacylation, Sir2La has a very high KM for NAD+ compared to the expected levels of the dinucleotide in L. acidophilus. Sir2La is the first sirtuin from Lactobacillales and of the Gram-positive bacterial subclass of sirtuins to be functionally characterized. The ability to hydrolyze propionyl- and butyryllysine emphasizes the relevance of further exploring the role of other short-chain acyl moieties as PTMs.