Histone deacetylase inhibitors (HDI) can inhibit proliferation and enhance apoptosis in a wide range of malignancies. However, HDIs show relatively modest activity in head and neck squamous cell carcinomas (HNSCC), in which we have shown the activation of nuclear factor-kappaB (NF-kappaB; NF-kappaB1/RelA or p50/p65), a transcription factor that promotes expression of proliferative and antiapoptotic genes. In this study, we examined if HDIs enhance activation of NF-kappaB and target genes and if genetic or pharmacologic inhibition of NF-kappaB can sensitize HNSCC to HDIs. Limited activity of classic HDIs trichostatin A and sodium butyrate was associated with enhanced activation of NF-kappaB reporter activity in a panel of six HNSCC cell lines. HDIs enhanced NF-kappaB p50/p65 DNA binding and acetylation of the RelA p65 subunit. Transfection of small interfering RNAs targeting p65 strongly inhibited NF-kappaB expression and activation, induced cell cycle arrest and cell death, and further sensitized HNSCC cells when combined with HDIs. The p65 small interfering RNA inhibited HDI-enhanced expression of several NF-kappaB-inducible genes implicated in oncogenesis of HNSCC, such as p21, cyclin D1, and BCL-XL. Bortezomib, an inhibitor of proteasome-dependent NF-kappaB activation, also increased sensitization to trichostatin A, sodium butyrate, and a novel HDI, PXD101, in vitro, and to the antitumor effects of PXD101 in bortezomib-resistant UMSCC-11A xenografts. However, gastrointestinal toxicity, weight loss, and mortality of the combination were dose limiting and required parenteral fluid administration. We conclude that HDI-enhanced NF-kappaB activation is one of the major mechanisms of resistance of HNSCC to HDIs. The combination of HDI and proteasome inhibitor produced increased antitumor activity. Low starting dosages for clinical studies combining HDIs with proteasome inhibitors and IV fluid support may be warranted.