GO:0031065:   positive regulation of histone deacetylation
Any process that activates or increases the frequency, rate or extent of the removal of acetyl groups from histones.