Histone deacetylases (HDACs) are enzymes involved in the remodelling of chromatin, and have a key role in the epigenetic regulation of gene expression. In addition, the activity of non-histone proteins can be regulated through HDAC-mediated hypo-acetylation. In recent years, inhibition of HDACs has emerged as a potential strategy to reverse aberrant epigenetic changes associated with cancer, and several classes of HDAC inhibitors have been found to have potent and specific anticancer activities in preclinical studies. However, such studies have also indicated that the effects of HDAC inhibitors could be considerably broader and more complicated than originally understood. Here we summarize recent advances in the understanding of the molecular events that underlie the anticancer effects of HDAC inhibitors, and discuss how such information could be used in optimizing the development and application of these agents in the clinic, either as monotherapies or in combination with other anticancer drugs.