It has been hypothesized that cancers originate from a small population of cells with stem cell-like characteristics, including self-renewal and pluripotency. Such tumor-initiating cells, also referred to as cancer stem cells, are thought to account for relapses following seemingly successful treatments, because their slow turnover and capacity for expelling anti-tumor drugs leaves them untouched by conventional treatment regimens. Targeting of cancer stem cells might be key for improving survival and producing cures in patients with metastatic tumors. Viruses enter cells though infection and might therefore not be sensitive to stem cell resistance mechanisms. During the last decades, oncolytic adenoviruses have been shown to effectively kill cancer cells, by seizing control of their DNA replication machinery and utilizing it for the production of new virions, ultimately resulting in the rupture of the cell. Human safety data in cancer trials has been excellent even when the dose of administered adenovirus has been high. Future approaches include additional modifications of the adenoviral genome that prime them to attack cancer stem cells specifically, utilizing linage-specific cell surface markers, dysfunctional stem cell signaling pathways or up-regulated oncogenic genes. However, already existing oncolytic adenoviruses have displayed potential to efficiently kill not only differentiated cancer cells, but also tumor-initiating stem cells. Here, we review the current literature that supports the existence of cancer stem cells and discuss the potential of virotherapy for killing tumor-initiating cells.