Replication-competent adenovirus (RCAd) constitutes an alternative in cancer therapy. For obtaining advanced RCAd generations with high oncolytic capability and a good safety profile, we constructed an E2F promoter-regulated RCAd carrying p16 gene, AdE2F-p16, in which the E1a gene was controlled by the E2F promoter. The experimental data showed that the E2F promoter endowed AdE2F-p16 with high specificity in cancer cells. While rarely replicating in normal cells, AdE2F-p16 could replicate in p16-deficient cancer cells, with 2,937- to 160,000-fold increased replicative capability in different cancer cell lines. AdE2F-p16 expressed p16 within cancer cells and led to potent antitumor efficacy in gastric cancer xenografts in nude mice, with a tumor inhibition rate of 59.14%. Due to the combined effects of cancer cell apoptosis induced by p16 expression and oncolysis by virus replication, the E2F promoter-regulated, p16-armed RCAd provides a promising strategy for cancer gene therapy.