Gene-modified replication-competent adenoviruses (Ads) are emerging as a promising new modality for the treatment of cancer. We have previously shown that E1B 19kDa and E1B 55kDa gene deleted Ad $(Ad-{Delta}E1B19/55)$ exhibits improved tumor-specific replication and cell lysis, leading to potent anti-tumor effect. As an additional effort to increase cancer cell-selectivity of replicating adenovirus, we have first generated eleven E1A-mutant Ads $(Ad-mt{sharp}1{sim}{sharp}11)$ with deletion or substitution in retinoblastoma (Rb) binding sites of E1A. Of these viruses, $Ad-mt{sharp}7$ demonstrated Significantly improved cytopathic effect (CPE) and viral replication in a cancer cell-specific manner. To further increase the cancer cell-specific killing effect of $Ad-mt{sharp}7$, both E1B 19kDa and E1B 55kDa genes were deleted, resulting in an $Ad-{Delta}E1Bmt7$. As assessed using CPE assay, MTT assay, and immunoblot analysis for Ad fiber expression, $Ad-{Delta}$ E1Bmt7 exerted markeldly enhanced cancer cell-specific killing effect as well as viral replication in comparison to either $Ad-mt{sharp}7$ or $Ad-{Delta}E1B19/55$. Furthermore, the growth of established human cervical carcinoma in nude mice was significantly suppressed by intratumoral injection of $Ad-{Delta}E1Bmt7$. In summary, we have developed an oncolytic adenovirus with significantly improved therapeutic profiles for cancer treatment.