Replication-selective oncolytic viruses are being developed for human cancer therapy. We previously developed an attenuated adenovirus (OBP-301, Telomelysin), in which the human telomerase reverse transcriptase promoter element drives expression of E1A and E1B genes linked with an internal ribosome entry site. OBP-301 can replicate in, and causes selective lysis of, human cancer cells. Valproic acid (VPA), which is an effective antiepileptic drug, is known to inhibit the histone deacetylase activities. We determined whether the antitumor effect of OBP-301 could be enhanced by VPA in human lung cancer cells. In an in vitro cell viability assay, OBP-301 infection killed four human lung cancer cell lines, H1299, H1299-R5 (a subline of H1299 with a low level of the coxsackievirus and adenovirus receptor (CAR) expression), H460, and A549, more efficiently in the presence of VPA than in its absence. VPA treatment increased CAR expression in all the four lung cancer cells. Consistent with their CAR upregulation, the infection efficiency of adenoviruses in the presence of VPA was significantly higher than that in its absence. The molecular mechanism of this combined effect could be explained by an increase in adenovirus infectivity via VPA-mediated upregulation of CAR. These results suggest that treatment with OBP-301 in combination with VPA is a promising strategy for human lung cancer.