Cancer stem cells (CSCs) are defined as rare populations of tumor-initiating cancer cells that are capable of both self-renewal and differentiation. Extensive research is currently underway to develop therapeutics that target CSCs for cancer therapy, due to their critical role in tumorigenesis, as well as their resistance to chemotherapy and radiotherapy. To this end, oncolytic viruses targeting unique CSC markers, signaling pathways, or the pro-tumor CSC niche offer promising potential as CSCs-destroying agents/therapeutics. We provide a summary of existing knowledge on the biology of CSCs, including their markers and their niche thought to comprise the tumor microenvironment, and then we provide a critical analysis of the potential for targeting CSCs with oncolytic viruses, including herpes simplex virus-1, adenovirus, measles virus, reovirus, and vaccinia virus. Specifically, we review current literature regarding first-generation oncolytic viruses with their innate ability to replicate in CSCs, as well as second-generation viruses engineered to enhance the oncolytic effect and CSC-targeting through transgene expression.