In our search for novel small molecules targeting histone deacetylases, we have designed and synthesized several series of novel N-hydroxybenzamides/N-hydroxypropenamides incorporating quinazolin-4(3H)-ones (4a-h, 8a-d, 10a-d). Biological evaluation showed that these hydroxamic acids were generally cytotoxic against three human cancer cell lines (SW620, colon; PC-3, prostate; NCI-H23, lung cancer). It was found that the N-hydroxypropenamides (10a-d) were the most potent, both in term of HDAC inhibition and cytotoxicity. Several compounds, e.g. 4e, 8b-c, and 10a-c, displayed up to 4-fold more potent than SAHA (suberoylanilide hydroxamic acid, vorinostat) in term of cytotoxicity. These compounds also comparably inhibited HDACs with IC50 values in sub-micromolar range. Docking experiments on HDAC2 isozyme revealed some important features contributing to the inhibitory activity of synthesized compounds, especially for propenamide analogues. Importantly, the free binding energy computed was found to have high quantitative correlation (R2 ∼ 95%) with experimental results.