The tumor microenvironment is complex with the cancer stem cell (CSC) as a member within its community. This population possesses the capacity to self-renew and to cause cellular heterogeneity of the tumor. CSCs are resistant to conventional anti-proliferative drugs. In order to be curative, it is imperative that CSCs must be eliminated by cancer therapy. A variety of dietary phytochemicals and repositioned drugs can act synergistically with conventional anti-cancer agents. In this review, we advocate the development of a novel approach, namely combination therapy by incorporating both phytochemicals and repositioned drugs to target CSCs. We cover select dietary phytochemicals (curcumin, resveratrol, EGCG, genistein) and repurposed drugs (metformin, niclosamide, thioridazine, chloroquine). Five of the eight (curcumin, resveratrol, EGCG, genistein, metformin) are listed in "The Halifax Project", that explores "the concept of a low-toxicity 'broad-spectrum' therapeutic approach that could simultaneously target many key pathways and mechanisms" [1]. For these compounds, we discuss their mechanisms of action, in which models their anti-CSC activities were identified, as well as advantages, challenges and potentials of combination therapy.