Initially regarded as “epigenetic modifiers” acting predominantly through chromatin remodeling via histone acetylation, HDACIs, alternatively referred to as lysine deacetylase or simply deacetylase inhibitors, have since been recognized to exert multiple cytotoxic actions in cancer cells, often through acetylation of non-histone proteins. Some well-recognized mechanisms of HDACI lethality include, in addition to relaxation of DNA and de-repression of gene transcription, interference with chaperone protein function, free radical generation, induction of DNA damage, up-regulation of endogenous inhibitors of cell cycle progression, e.g., p21, and promotion of apoptosis. Intriguingly, this class of agents is relatively selective for transformed cells, at least in pre-clinical studies. In recent years, additional mechanisms of action of these agents have been uncovered. For example, HDACIs interfere with multiple DNA repair processes, as well as disrupt cell cycle checkpoints, critical to the maintenance of genomic integrity in the face of diverse genotoxic insults. Despite their pre-clinical potential, the clinical use of HDACIs remains restricted to certain subsets of T-cell lymphoma. Currently, it appears likely that the ultimate role of these agents will lie in rational combinations, only a few of which have been pursued in the clinic to date. This review focuses on relatively recently identified mechanisms of action of HDACIs, with particular emphasis on those that relate to the DNA damage response (DDR), and discusses synergistic strategies combining HDACIs with several novel targeted agents that disrupt the DDR or antagonize anti-apoptotic proteins that could have implications for the future use of HDACIs in patients with cancer.