Sirtuin enzymes depend on NAD+ to catalyze protein deacetylation. Therefore, the lowering of NAD+ during aging leads to decreased sirtuin activity and may speed up aging processes in laboratory animals and humans. In this study, we used a genetic screen to identify two mutations in the catalytic domain of yeast Sir2 that allow the enzyme to function in an NAD+-depleted environment. These mutant enzymes give rise to a significant increase of yeast replicative lifespan and increase deacetylation by the Sir2 ortholog, SIRT1, in mammalian cells. Our data suggest that these mutations increase the stability of the conserved catalytic sirtuin domain, thereby increasing the catalytic efficiency of the mutant enzymes. Our approach to identifying sirtuin mutants that permit function in NAD+-limited environments may inform the design of small molecules that can maintain sirtuin activity in aging organisms.