Over the past decade, human histone deacetylases (HDACs) have become interesting as therapeutic targets because of the benefits that their modulation might provide in aging-related disorders. Recently, studies using crystallography and computational chemistry have provided information on the structure and conformational changes related to HDAC-mediated recognition events. Through the description of the key mass and one-off movements observed in metal-dependent HDACs, here we highlight the impact of flexibility on drug-binding affinity and specificity. The collected information will be useful for not only a better understanding of the biological functions of HDACs, but also the conception of new selective binders.