Genetic and epigenetic changes in DNA are involved in cancer development and tumor progression. Histone deacetylases (HDACs) are key regulators of gene expression that act as transcriptional repressors by removing acetyl groups from histones. HDACs are dysregulated in many cancers, making them a therapeutic target for the treatment of cancer. Histone deacetylase inhibitors (HDACi), a novel class of small-molecular therapeutics, are now approved by the Food and Drug Administration as anticancer agents. While they have shown great promise, resistance to HDACi is often observed and furthermore, HDACi have shown limited success in treating solid tumors. The combination of HDACi with standard chemotherapeutic drugs has demonstrated promising anticancer effects in both preclinical and clinical studies. In this review, we summarize the research thus far on HDACi in combination therapy, with other anticancer agents and their translation into preclinical and clinical studies. We additionally highlight the side effects associated with HDACi in cancer therapy and discuss potential biomarkers to either select or predict a patient's response to these agents, in order to limit the off-target toxicity associated with HDACi.