Myeloid-derived suppressor cells (MDSCs) contribute to the induction of an immune suppressive/anergic, tumor permissive environment. MDSCs act as immunosuppression orchestrators also by interacting with several components of both innate and adaptive immunity. Natural killer (NK) cells are innate lymphoid cells functioning as primary effector of immunity, against tumors and virus-infected cells. Apart from the previously described anergy and hypo-functionality of NK cells in different tumors, NK cells in cancer patients show pro-angiogenic phenotype and functions, similar to decidual NK cells. We termed the pro-angiogenic NK cells in the tumor microenvironment “tumor infiltrating NK” (TINKs), and peripheral blood NK cells in cancer patients “tumor associated NK” (TANKs). The contribution of MDSCs in regulating NK cell functions in tumor-bearing host, still represent a poorly explored topic, and even less is known on NK cell regulation of MDSCs. Here, we review whether the crosstalk between MDSCs and NK cells can impact on tumor onset, angiogenesis and progression, focusing on key cellular and molecular interactions. We also propose that the similarity of the properties of tumor associated/tumor infiltrating NK and MDSC with those of decidual NK and decidual MDSCs during pregnancy could hint to a possible onco-fetal origin of these pro-angiogenic leukocytes.