The treatment of tumor cells with HDAC inhibitors (HDACi) induces a range of effects including apoptosis, cell cycle arrest, differentiation and senescence, modulation of immune response, and altered angiogenesis. The single-agent activities of several HDACi have been tested in preclinical and clinical studies and are currently the subject of ongoing clinical trials. Although HDACi have been shown to be effective as a single agent against a defined subset of hematological tumors, less convincing results have been found in the treatment of solid tumors. Since current clinical trials of single-agent HDACi showed limited efficacy, in this review we focus on drug combinations including HDACi with conventional chemotherapeutic agents and novel targeted agents. Particular emphasis has been devoted to combinations effective in solid tumors and to combinations between HDACi and immunotherapies. An outline of novel combination strategies, including a new generation of more potent and specific HDACi (e.g., compounds with adamantine and noradamantane as scaffolds) as well as chemical hybrid molecules, has been provided. The paradoxical role of HDACs as tumor suppressors in developing tumors and as therapeutic targets in established neoplasms has also been considered.