Histone deacetylase inhibitors (HDACi) are potent anti-cancer agents for variety of cancer types. Suberoylanilide hydroxamic acid (SAHA) has been approved as a drug to treat cutaneous T cell lymphoma, and the combination of HDACi and other agents have been actively tested in many clinical trials. Adenovirus 5 early region 1A (E1A) has been shown to exhibit high tumor suppressor activity, and gene therapy using E1A has been tested in clinical trials. Here, we showed that proapoptotic activity of HDACi was robustly enhanced by E1A in multiple cancer cells, but not in normal cells. Moreover, we showed that combination of E1A gene therapy and SAHA showed high therapeutic efficacy with low toxicity in vivo ovarian and breast xenograft models. SAHA downregulated Bcl-XL and upregulated proapoptotic BH3-only protein Bim, whose expression was further enhanced by E1A in cancer cells. These alterations of Bcl-2 family proteins were critical for apoptosis induced by the combination in cancer cells. SAHA enhanced acetylation of histone H3 in Bim promoter region, while E1A upregulated Egr-1, which was directly involved in Bim transactivation. Together, our results provide not only a novel insight into the mechanisms underlying anti-tumor activity of E1A, but also a rationale for the combined HDACi and E1A gene therapy in future clinical trials.