Sirtuin proteins comprise a unique class of NAD(+)-dependent protein deacetylases. Although several structures of sirtuins have been determined, the mechanism by which NAD(+) cleavage occurs has remained unclear. We report the structures of ternary complexes containing NAD(+) and acetylated peptide bound to the bacterial sirtuin Sir2Tm and to a catalytic mutant (Sir2TM(H116Y)). NAD(+) in these structures binds in a conformation different from that seen in previous structures, exposing the alpha face of the nicotinamide ribose to the carbonyl oxygen of the acetyl lysine substrate. The NAD+ conformation is identical in both structures, suggesting that proper coenzyme orientation is not dependent on contacts with the catalytic histidine. We also present the structure of Sir2TM(H116A) bound to deacteylated peptide and 3'-O-acetyl ADP ribose. Taken together, these structures suggest a mechanism for nicotinamide cleavage in which an invariant phenylalanine plays a central role in promoting formation of the O-alkylamidate reaction intermediate and preventing nicotinamide exchange.