The epigenome of cancer cells is determined by DNA methylation and an array of post-translational modifications of the core histones. Epigenetic abnormalities are commonly found in human tumors and importantly, they can be reversed by pharmacologic inhibitors. Histone deacetylase inhibitors (HDACIs) represent one of the most promising epigenetic treatments for cancer. HDACIs have emerged as promising targets for cancer therapy because they reactivate the transcription of multiple genes that are silenced in human tumors and they show pleiotropic anti-tumor effects selectively in cancer cells. HDACIs are well-tolerated and several show promising anti-tumor activity. While gene transcription has been considered to be the major target of HDACIs, inhibition of acetylation of non-histone proteins is now emerging as a novel basis for their anti-tumor effects. In this review, we discuss new insights into the molecular mechanism of HDACIs, their current status of clinical development, and possible future uses in cancer therapy.