HDACs (histone deacetylases) are considered to be among the most important enzymes that regulate gene expression in eukaryotic cells. In general, increased levels of histone acetylation are associated with increased transcriptional activity, whereas decreased levels are linked to repression of gene expression. HDACs associate with a number of cellular oncogenes and tumour-suppressor genes, leading to an aberrant recruitment of HDAC activity, which results in changes of gene expression, impaired differentiation and excessive proliferation of tumour cells. Therefore HDAC inhibitors are efficient anti-proliferative agents in both in vitro and in vivo pre-clinical models of cancer, making them promising anticancer therapeutics. In the present paper, we present the results of a medium-throughput screening programme aiming at the identification of novel HDAC inhibitors using HDAH (HDAC-like amidohydrolase) from Bordetella or Alcaligenes strain FB188 as a model enzyme. Within a library of 3719 compounds, several new classes of HDAC inhibitor were identified. Among these hit compounds, there were also potent inhibitors of eukaryotic HDACs, as demonstrated by an increase in histone H4 acetylation, accompanied by a decrease in tumour cell metabolism in both SHEP neuroblastoma and T24 bladder carcinoma cells. In conclusion, screening of a compound library using FB188 HDAH as model enzyme identified several promising new lead structures for further development.