The extra virgin olive oil (EVOO) dihydroxy-phenol oleacein is a natural inhibitor of multiple metabolic and epigenetic enzymes capable of suppressing the functional traits of cancer stem cells (CSC). Here, we used a natural product-inspired drug discovery approach to identify new compounds that phenotypically mimic the anti-CSC activity of oleacein. We coupled 3D quantitative structure-activity relationship-based virtual profiling with phenotypic analysis using 3D tumorsphere formation as a gold standard for assessing the presence of CSC. Among the top 20 computationally-predicted oleacein mimetics, four fulfilled the phenotypic endpoint of specifically suppressing the tumorsphere-initiating capacity of CSC, in the absence of significant cytotoxicity against differentiated cancer cells growing in 2D cultures in the same low micromolar concentration range. Of these, 3,4-dihydrophenetyl butyrate –a lipophilic ester conjugate of the hydroxytyrosol moiety of oleacein– and (E)-N-allyl-2-((5-nitrofuran-2-yl)methylene)hydrazinecarbothioamide) –an inhibitor of Trypanosoma cruzi triosephosphate isomerase– were also highly effective at significantly reducing the proportion of aldehyde dehydrogenase (ALDH)-positive CSC-like proliferating cells. Preservation of the mTOR/DNMT binding mode of oleacein was dispensable for suppression of the ALDH+-CSC functional phenotype in hydroxytyrosol-unrelated mimetics. The anti-CSC chemistry of complex EVOO phenols such as oleacein can be phenocopied through the use of mimetics capturing its physico-chemical properties.