GO:0017136:   NAD-dependent histone deacetylase activity
Catalysis of the reaction: histone N6-acetyl-L-lysine + H2O = histone L-lysine + acetate. This reaction requires the presence of NAD, and represents the removal of an acetyl group from a histone.