Tumor microenvironment (TME) consisting of distinct cell types including stromal cells and immune cells has recently emerged as a pivotal player in tumor development and progression. Mesenchymal stromal cells (MSCs) and tumor-associated macrophages (TAMs) are two representative cells in the TME with plastic properties. This review will focus on the evolution of phenotypes and functions of either MSCs or TAMs, which is "educated" by the TME, as well as interactions between MSCs and TAMs contributing to the distinct stages of tumor biology in gastric cancer. MSCs exert immunoregulatory effects on macrophages and polarize them toward M2-like TAMs, via cell-cell contact and paracrine or extracellular vesicle (EV) transfer mechanism. In turn, M2-TAMs modulate the transition of "naive" MSCs into tumor-derived MSCs, which possess a more potent pro-tumor role than the parent. Moreover, the cross talk between MSCs and TAMs could contribute to cancer biology by inducing the EMT process, metastasis, immune invasion, and immunotherapy resistance in cancer cells. However, molecular mechanisms underlying interactions between MSCs and TAMs in gastric cancer progression need to be thoroughly elucidated, which may provide attractive targets for making promising novel strategies for gastric cancer therapy.