Myeloid-derived suppressor cells (MDSC) contribute to immune suppression in cancer, but the mechanisms through which they drive metastatic progression are not fully understood. In this study, we show how MDSC convey stem-like qualities to breast cancer cells that coordinately help enable immune suppression and escape. We found that MDSC promoted tumor formation by enhancing breast cancer cell stem-like properties as well as by suppressing T-cell activation. Mechanistic investigations indicated that these effects relied upon cross-talk between the STAT3 and NOTCH pathways in cancer cells, with MDSC inducing IL6-dependent phosphorylation of STAT3 and activating NOTCH through nitric oxide leading to prolonged STAT3 activation. In clinical specimens of breast cancer, the presence of MDSC correlated with the presence of cancer stem-like cells (CSC) and independently predicted poor survival outcomes. Collectively, our work revealed an immune-associated mechanism that extrinsically confers cancer cell stemness properties and affects patient outcome. We suggest that targeting STAT3-NOTCH cross-talk between MDSC and CSC could offer a unique locus to improve cancer treatment, by coordinately targeting a coupled mechanism that enables cancer stemness and immune escape. Cancer Res; 76(11); 3156–65. ©2016 AACR.