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.