Recent studies have implicated multipotential mesenchymal stem cells (MSCs) as an aid to breast cancer cell proliferation and metastasis, partly as a result of the MSCs secretome. As the tumor gets beyond 2 mm in diameter, the stromal cells could undergo starvation due to the lack of sufficient nutrients in solid tumor microenvironment. In this study, we investigated the survival mechanisms used by stressed stromal cells in breast cancers. We used serum-deprived mesenchymal stem cells (SD-MSCs) and MCF-7 breast cancer cells as model system with a hypothesis that stromal cells in the nutrient-deprived core utilize survival mechanisms for supporting surrounding cells. We tested this hypothesis using in vivo tumor xenografts in immunodeficient mice, which indicated that SD-MSCs supported MCF-7 tumor growth by protection from apoptosis. Histochemical assays showed that SD-MSCs-injected tumors exhibited higher cellularity, decreased apoptosis and decreased differentiation. Beclin-1 staining indicated autophagic areas surrounded by actively proliferating cells. Furthermore, in vitro studies demonstrate that SD-MSCs survive using autophagy and secrete paracrine factors that support tumor cells following nutrient/serum deprivation. Western blot and immunocytochemistry analysis of SD-MSCs demonstrated upregulation and perinuclear relocation of autophagy key regulators such as beclin-1, ATG10, ATG12, MAP-LC3 and lysosomes. Electron microscopic analysis detected a time-dependent increase in autophagosome formation and HDAC6 activity assays indicated the upregulation of autophagy. Taken together, these data suggest that under nutrient-deprived conditions that can occur in solid tumors, stromal cells utilize autophagy for survival and also secrete anti-apoptotic factors that can facilitate solid tumor survival and growth.