Histone deacetylases (HDACs) play an important role in gene transcription. Inhibitors of HDACs induce cell differentiation and suppress cell proliferation in tumor cells. AutoDock calculations of known and novel HDAC inhibitors as well as of several probe molecules to histone deacetylase-like protein (HDLP), using a modified scoring function for metalloproteins, demonstrate excellent agreement (R = 0.92) between experimental and computed binding constants. Analysis of the docked structures allows a determination of the different binding motifs in known inhibitors. Such calculations are a useful tool for the prediction of binding constants for new HDAC inhibitors. Exploration of the 14 A long internal cavity adjacent to the active site by docking of small molecular probes suggest that it plays a crucial role by accepting the cleaved acetate and releasing it at the far side of the cavity. The importance of the findings for the design of new inhibitors is discussed.