Sirtuin enzymes comprise a unique class of NAD(+)-dependent protein deacetylases. Although structures of many sirtuin complexes have been determined, structural resolution of intermediate chemical steps are needed to understand the deacetylation mechanism. We report crystal structures of the bacterial sirtuin, Sir2Tm, in complex with an S-alkylamidate intermediate, analogous to the naturally occurring O-alkylamidate intermediate, and a Sir2Tm ternary complex containing a dissociated NAD(+) analog and acetylated peptide. The structures and biochemical studies reveal critical roles for the invariant active site histidine in positioning the reaction intermediate, and for a conserved phenylalanine residue in shielding reaction intermediates from base exchange with nicotinamide. The new structural and biochemical studies provide key mechanistic insight into intermediate steps of the Sir2 deacetylation reaction.