The SIR2 protein family comprises a novel class of nicotinamide-adenine dinucleotide (NAD)-dependent protein deacetylases that function in transcriptional silencing, DNA repair, and life-span extension in Saccharomyces cerevisiae. Two crystal structures of a SIR2 homolog from Archaeoglobus fulgidus complexed with NAD have been determined at 2.1 A and 2.4 A resolutions. The structures reveal that the protein consists of a large domain having a Rossmann fold and a small domain containing a three-stranded zinc ribbon motif. NAD is bound in a pocket between the two domains. A distinct mode of NAD binding and an unusual configuration of the zinc ribbon motif are observed. The structures also provide important insights into the catalytic mechanism of NAD-dependent protein deacetylation by this family of enzymes.