Absent or altered differentiation is one of the major features of cancer cells. Histone deacetylases (HDACs) play a central role in the epigenetic regulation of gene expression. Aberrant activity of HDACs has been documented in several types of cancers, leading to the development of HDAC inhibitors (HDACi) as anti-tumor drugs. In vitro and in vivo experimental evidences show that HDACi are able to resume the process of maturation in undifferentiated cancer cells, justifying their introduction as differentiating agents in several clinical trials. Modulation of cell fate by HDACi is observed at several levels, including the stem cell compartment: HDACi can act both on cancer stem cells, and with the rest of the tumor cell mass, leading to complex biological outputs. As a note of caution, when used as single agent, HDACi show only a moderate and limited biological response, which is augmented in combinatorial therapies with drugs designed against other epigenetic targets. The optimal employment of these molecules may be therefore in combination with other epigenetic drugs acting against the set of enzymes responsible for the set-up and maintenance of epigenetic information.