Sir2 proteins form a family of NAD(+)-dependent protein deacetylases required for diverse biological processes, including transcriptional silencing, suppression of rDNA recombination, control of p53 activity, regulation of acetyl-CoA synthetase, and aging. Although structures of Sir2 enzymes in the presence and absence of peptide substrate or NAD(+) have been determined, the role of the enzyme in the mechanism of deacetylation and NAD(+) cleavage is still unclear. Here, we present additional structures of Sir2Af2 in several differently complexed states: in a productive complex with NAD(+), in a nonproductive NAD(+) complex with bound ADP-ribose, and in the unliganded state. We observe a new mode of NAD(+) binding that seems to depend on acetyl-lysine binding, in which the nicotinamide ring of NAD(+) is buried in the highly conserved "C" pocket of the enzyme. We propose a detailed structure-based mechanism for deacetylation and nicotinamide inhibition of Sir2 consistent with mutagenesis and enzymatic studies.