Combination therapy of adenoviral gene therapy and a histone deacetylase (HDAC) inhibitor is important due to the enhancing effect of HDAC inhibitors on adenoviral transduction and transcription. However, contradictory results have been reported on the effect of combination of CRAd (conditionally replicating adenovirus) and HDAC inhibitors. This study was designed to investigate the interaction of CRAd and HDAC inhibitors and determine the ideal way to combine the two agents. Combination of HDAC inhibitors (SK7041, SBHA and vorinostat) at pre- and post-transductional periods with CRAd enhanced the transduction of CRAd and expression of luciferase expression from Δ24-luc in vitro. However, suppression of luciferase expression from Δ24-luc injected tumor mass was observed by in vivo tumor bioluminescence imaging and drug interaction analysis also showed an antagonistic interaction that was probably related with the inhibitory effect of the HDAC inhibitor on adenoviral replication. Suppression of p21 induction by p21 siRNA reversed the suppressive effect of vorinostat on the replication of CRAd, but still failed to reverse the antagonistic interaction. Addition of vorinostat at the pre-transductional period revealed an improvement in the transduction efficiency of CRAd and also induced a synergistic interaction between CRAd and vorinostat, which was possibly related with prevention of the suppressive effect of vorinostat on adenoviral replication. In conclusion, the addition of HDAC inhibitor before CRAd injection showed synergistic antitumor effects, which warrants further investigation on the sequence of HDAC inhibitor and CRAd treatment in an animal tumor model.