Apart from their killer identity, natural killer (NK) cells have integral roles in shaping the tumor microenvironment. Through immune gene deconvolution, the present study revealed an interplay between NK cells and myeloid-derived suppressor cells (MDSCs) in nonresponders of immune checkpoint therapy. Given that the mechanisms governing the outcome of NK cell-to-myeloid cell interactions remain largely unknown, we sought to investigate the cross-talk between NK cells and suppressive myeloid cells. Upon contact with tumor-experienced NK cells, monocytes and neutrophils displayed increased expression of MDSC-related suppressive factors along with increased capacities to suppress T cells. These changes were accompanied by impaired antigen presentation by monocytes and increased ER stress response by neutrophils. In a cohort of patients with sarcoma and breast cancer, the production of interleukin-6 (IL-6) by tumor-infiltrating NK cells correlated with S100A8/9 and arginase-1 expression by MDSCs. At the same time, NK cell-derived IL-6 was associated with tumors with higher major histocompatibility complex class I expression, which we further validated with b2m-knockout (KO) tumor mice models. Similarly in syngeneic wild-type and IL-6 KO mouse models, we then demonstrated that the accumulation of MDSCs was influenced by the presence of such regulatory NK cells. Inhibition of the IL-6/signal transducer and activator of transcription 3 (STAT3) axis alleviated suppression of T cell responses, resulting in reduced tumor growth and metastatic dissemination. Together, these results characterize a critical NK cell-mediated mechanism that drives the development of MDSCs during tumor immune escape.