Simple Summary Breast cancer stem cells are a subset of transformed cells that sustain tumor growth and can metastasize to secondary organs. Since metastasis accounts for most cancer deaths, it is of paramount importance to understand the cellular and molecular mechanisms that regulate this subgroup of cells. The tumor microenvironment (TME) is the habitat in which transformed cells evolve, and it is composed by many different cell types and the extracellular matrix (ECM). A body of evidence strongly indicates that microenvironmental cues modulate stemness in breast cancer, and that the coevolution of the TME and cancer stem cells determine the fate of breast tumors. In this review, we summarize the studies providing links between the TME and the breast cancer stem cell phenotype and we discuss their specific interactions with immune cell subsets, stromal cells, and the ECM. Tumor progression involves the co-evolution of transformed cells and the milieu in which they live and expand. Breast cancer stem cells (BCSCs) are a specialized subset of cells that sustain tumor growth and drive metastatic colonization. However, the cellular hierarchy in breast tumors is rather plastic, and the capacity to transition from one cell state to another depends not only on the intrinsic properties of transformed cells, but also on the interplay with their niches. It has become evident that the tumor microenvironment (TME) is a major player in regulating the BCSC phenotype and metastasis. The complexity of the TME is reflected in its number of players and in the interactions that they establish with each other. Multiple types of immune cells, stromal cells, and the extracellular matrix (ECM) form an intricate communication network with cancer cells, exert a highly selective pressure on the tumor, and provide supportive niches for BCSC expansion. A better understanding of the mechanisms regulating these interactions is crucial to develop strategies aimed at interfering with key BCSC niche factors, which may help reducing tumor heterogeneity and impair metastasis.