Tumor heterogeneity is considered the major cause of treatment failure in current cancer therapies. This feature of solid tumors is not only the result of clonal outgrowth of cells with genetic mutations, but also of epigenetic alterations induced by physical and chemical signals from the tumor microenvironment (TME). Besides fibroblasts, endothelial and immune cells, mesenchymal stroma/stem-like cells (MSCs) and tumor-associated macrophages (TAMs) intimately crosstalk with cancer cells and can exhibit both anti-and pro-tumorigenic effects. MSCs can alter cancer cellular phenotypes to increase cancer cell plasticity, eventually resulting in the generation of cancer stem cells (CSCs). The shift between different phenotypic states (phenotype switching) of CSCs is controlled via both genetic programs, such as epithelial-mesenchymal transdifferentiation or retrodifferentiation, and epigenetic alterations triggered by signals from the TME, like hypoxia, spatial heterogeneity or stromal cell-derived chemokines. Finally, we highlight the role of spontaneous cancer cell fusion with various types of stromal cells. i.e., MSCs in shaping CSC plasticity. A better understanding of cell plasticity and phenotype shifting in CSCs is a prerequisite for exploiting this phenomenon to reduce tumor heterogeneity, thereby improving the chance for therapy success.