Targeting tumor-initiating, drug-resistant populations of cancer stem cells (CSC) with phytochemicals is a novel paradigm for cancer prevention and treatment. We herein employed a phenotypic drug discovery approach coupled to mechanism-of-action profiling and target deconvolution to identify phenolic components of extra virgin olive oil (EVOO) capable of suppressing the functional traits of CSC in breast cancer (BC). In vitro screening revealed that the secoiridoid decarboxymethyl oleuropein aglycone (DOA) could selectively target subpopulations of epithelial-like, aldehyde dehydrogenase (ALDH)-positive and mesenchymal-like, CD44+CD24-/low CSC. DOA could potently block the formation of multicellular tumorspheres generated from single-founder stem-like cells in a panel of genetically diverse BC models. Pretreatment of BC populations with noncytotoxic doses of DOA dramatically reduced subsequent tumor-forming capacity in vivo. Mice orthotopically injected with CSC-enriched BC-cell populations pretreated with DOA remained tumor-free for several months. Phenotype microarray-based screening pointed to a synergistic interaction of DOA with the mTOR inhibitor rapamycin and the DNA methyltransferase (DNMT) inhibitor 5-azacytidine. In silico computational studies indicated that DOA binds and inhibits the ATP-binding kinase domain site of mTOR and the S-adenosyl-l-methionine (SAM) cofactor-binding pocket of DNMTs. FRET-based Z-LYTE™ and AlphaScreen-based in vitro assays confirmed the ability of DOA to function as an ATP-competitive mTOR inhibitor and to block the SAM-dependent methylation activity of DNMTs. Our systematic in vitro, in vivo and in silico approaches establish the phenol-conjugated oleoside DOA as a dual mTOR/DNMT inhibitor naturally occurring in EVOO that functionally suppresses CSC-like states responsible for maintaining tumor-initiating cell properties within BC populations.