Gene therapy of cancer using adenovirus as a single treatment modality has met limited success and efforts to enhance therapeutic outcomes have included combination of gene therapy with chemotherapy. The goal of this study was to investigate which chemotherapeutic agents may be suitable for combination with gene therapy of prostate cancer. Using an adenovirus expressing green fluorescent protein (GFP), we determined the effect of cisplatin, gemcitabine, doxorubicin, depsipeptide and MS-275 on adenoviral infectivity and transgene expression in LNCaP cells. We found that the two histone deacetylase inhibitors (HDACi), depsipeptide and MS-275, and to a lesser extent doxorubicin, increased infectivity and transgene expression. However, only the HDACi selectively increased infectivity in LNCaP cells while doxorubicin increased infectivity to a greater extent in normal prostate epithelial cells (PrEC). The increase in infectivity but not transgene expression correlated to increased surface expression of coxsackie and adenovirus receptor (CAR). Increased transgene expression following infection with an adenovirus expressing tumor necrosis factor-related apoptosis inducing ligand (TRAIL) was observed only in LNCaP cells treated with depsipeptide or MS-275. Combination of TRAIL gene therapy with HDACi but not doxorubicin resulted in increased induction of apoptosis in LNCaP cells. In contrast, apoptosis was not enhanced by HDACi in normal PrEC. These results suggest that combination of HDACi with adenoviral TRAIL gene therapy may be a new therapeutic approach for the treatment of prostate cancer that warrants further investigation.