Cells with stem cell-like attributes, such as self-renewal and pluripotency, have been isolated from hematological malignancies and from several solid tumor types. Tumor-initiating cells, also referred to as cancer stem cells, are thought to be responsible for the initiation and growth of tumors. Like their normal counterparts, putative cancer stem cells show remarkable resistance to radiation and chemotherapy. Their capacity for surviving apparently curative treatment can result in tumor relapse. Novel approaches that target tumor-initiating cells in addition to differentiated malignant cells, which constitute the bulk of the tumor, are required for improved survival of patients with metastatic tumors. Oncolytic viruses enter cells through infection and may therefore be resistant to defense mechanisms exhibited by cancer stem cells. Oncolytic adenoviruses can be engineered to attack tumor stem cells, recognized by linage-specific cell surface markers, dysfunctional stem cell-signaling pathways, or upregulated oncogenic genes. Normal stem cells may possess innate resistance to adenoviruses, as most humans have sustained numerous infections with various wild-type serotypes. This review focuses on current literature in support of cancer stem cells and discusses the possibility of using oncolytic virotherapy for killing these tumor-initiating cells.