Acetylation and deacetylation of chromatin histone protein by histone deacetylase (HDAC) alters chromatin structure and dynamically affects transcriptional regulation. Many lines of evidence indicate that histone hypo-acetylation induces repression of tumour suppressor gene expression. Small molecule inhibitors of HDAC (HDACI) are highly effective in up-regulating tumour suppressor gene expression, reducing tumour growth and inducing programmed cell death in vitro and in cancer patients in phase I and II clinical trials. HDACI-induced growth inhibition and cytotoxicity have been attributed to acetylation of both histone and non-histone proteins. Less studied, but equally important, is the role of HDAC and HDACI on other components of the malignant phenotype: tumour initiation and progression. In this review, we summarise evidence indicating that the in vivo anti-cancer efficacy of HDACIs is at least in part dependent on suppression of cancer cell migration, invasion, metastasis, blood supply, and angiogenesis. As histone hypo-acetylation is involved in the tumourigenesis of various haematological and solid malignancies, the clinical use of HDACIs in patients at high risk of cancer or with precancerous conditions warrants further investigation.