Resistance to chemotherapy is still a challenge for the treatment of acute myeloid leukemia. Combination use of histone deacetylase inhibitors (HDACIs) and proteasome inhibitors may provide a potential way to overcome drug resistance. One of the HDACIs, valproic acid (VPA), and a proteasome inhibitor, bortezomib (BOR), were assessed. Co-exposure of cells to VPA and BOR inhibited proliferation, arrested the cell cycle in G0-G1 phase and induced apoptosis in both HL60 and HL60A cells. These events were accompanied by the inhibition of cyclin D1 and human telomerase reverse transcriptase (hTERT) as well as telomerase activity. Moreover, synergism of proliferation inhibition was found in HL60A, superior to the additivity in HL60. The effects of combination treatment on cell cycle arrest and telomerase activity inhibition in HL60A were also more striking than those in HL60. In summary, our findings provide an insight into future clinical applications of the VPA-BOR combination regimen for AML, especially in those cases which are resistant to conventional chemotherapy.