GO:0042826: histone deacetylase binding
Interacting selectively and non-covalently with the enzyme histone deacetylase.