Histone deacetylase inhibitors (HDACi) demonstrate considerable in vitro and in vivo activity and clinical efficacy in the treatment of hematological malignancies. Pre-clinical and early phase clinical trials identify therapeutic activity using a combination of HDACi and demethylating agents which may be more efficacious than single agent treatment. Our studies aimed to determine the effects and molecular mechanisms of action of novel hydroxamate (MCT-3) and benzamide [MGCD0103 (MG)] HDACi's in the HL-60 cell line alone and in combination with the demethylating agent 5-aza-cytidine (AZA). MG, MCT-3 and AZA treatment significantly inhibited HL-60 cell growth in vitro with MG being the most potent agent. MG in combination with AZA demonstrated no significant increase in inhibition of cell growth over MG treatment alone whilst MCT-3 in combination with AZA demonstrated increased inhibition of cell growth over either agent alone although no more significant than MG alone. MG alone or MCT-3 in combination with AZA significantly increased p15 and caspase-3 expression. MG and MCT-3 significantly attenuated AZA-induced MMP-9 mRNA expression and proteolytic activity. Interestingly, MCT-3, MG and AZA alone and in combination increased expression of the novel tumour suppressor gene Nur77, important in leukemogenesis, with MG a more potent inducer as a single agent. These observations suggest the enhanced anti-leukemia activity of the combination of AZA and HDACi may only reside with certain HDACi classes and may be in-part explained by regulation of genes associated with cell cycle arrest, apoptosis and tumour suppression.