Epigenic modifications, mainly DNA methylation and acetylation, are recognized as the main mechanisms contributing to the malignant phenotype. Acetylation and deacetylation are catalyzed by specific enzymes, histone acetyltransferases (HATs) and histone deacetylases (HDACs), respectively. While histones represent a primary target for the physiological function of HDACs, the antitumor effect of HDAC inhibitors might also be attributed to transcription-independent mechanisms by modulating the acetylation status of a series of non-histone proteins. HDAC inhibitors may act through the transcriptional reactivation of dormant tumor suppressor genes. They also modulate expression of several other genes related to cell cycle, apoptosis, and angiogenesis. Several HDAC inhibitors are currently in clinical trials both for solid and hematologic malignancies. Thus, HDAC inhibitors, in combination with DNA-demethylating agents, chemopreventive, or classical chemotherapeutic drugs, could be promising candidates for cancer therapy. Here, we review the molecular mechanisms and therapeutic potential of HDAC inhibitors for the treatment of cancer.