Histone deacetylase inhibitors (HDACi) are a promising new class of chemotherapeutic drug currently in early phase clinical trials. A large number of structurally diverse HDACi have been purified or synthesised that mostly inhibit the activity of all eleven class I and II HDACs. While these agents demonstrate many features required for anti-cancer activity such as low toxicity against normal cells and an ability to inhibit tumor cell growth and survival at nanomolar concentrations, their mechanisms of action are largely unknown. Initially, a model was proposed whereby HDACi-mediated transactivation of a specific gene or set of genes was responsible for the inhibition of cell cycle progression or induction of apoptosis. Given that HDACs can regulate the activity of a number of nonhistone proteins and that histone acetylation is important for events such as DNA replication and mitosis that do not directly involve gene transcription, it appears that the initial mechanistic model for HDACi may have been too simple. Herein, we provide an update on the transcription-dependent and -independent events that may be important for the anti-tumor activities of HDACi and discuss the use of these compounds in combination with other chemotherapeutic drugs.