In the present study, we aimed to elucidate the mechanism responsible for the interactive effects of histone deacetylase (HDAC) inhibitors [suberoylanilide hydroxamic acid (SAHA), MS-275, m-carboxycinnamic acid bishydroxamide (CBHA), and trichostatin-A (TSA)] and tumor necrosis factor (TNF)-related apoptosis-inducing ligand (TRAIL) on apoptosis in leukemia cells. HDAC inhibitors enhance the apoptosis-inducing potential of TRAIL in leukemia cells (HL60, Jurkat, K562, and U937) through multiple mechanisms; up-regulation of DR4, DR5, Bak, Bax, Bim, Noxa and PUMA, down-regulation of IAPs, Mcl-1, Bcl-2, Bcl-XL and cFLIP, release of mitochondrial proteins (cytochrome c, Smac/DIABLO and Omi/Htr2) to the cytosol, induction of p21WAF1/CIP1 and p27KIP1, activation of caspase-3 and cleavage of poly(ADP-ribose) polymerase (PARP). The sequential treatment of cells with HDAC inhibitors followed by TRAIL was more effective in inducing apoptosis than the concurrent treatment or single agent alone. The up-regulation of death receptors and inhibition of cFLIP by HDAC inhibitors will increase the ability of TRAIL to induce apoptosis, due to enhance activation of caspase-8, cleavage of Bid, and release of mitochondrial proteins to the cytosol, and subsequent activation of caspase-9 and caspase-3. Thus, the combination of HDAC inhibitors and TRAIL can be used as a new therapeutic approach for the treatment of leukemia.