Immunotherapy has transformed cancer treatment by promoting durable clinical responses in a proportion of patients; however, treatment still fails in many patients. Innate immune cells play a key role in the response to immunotherapy. Crosstalk between innate and adaptive immune systems drives T-cell activation but also limits immunotherapy response, as myeloid cells are commonly associated with resistance. Hence, innate cells have both negative and positive effects within the tumor microenvironment (TME), and despite investment in early clinical trials targeting innate cells, they have seen limited success. Suppressive myeloid cells facilitate metastasis and immunotherapy resistance through TME remodeling and inhibition of adaptive immune cells. Natural killer (NK) cells, in contrast, secrete inflammatory cytokines and directly kill transformed cells, playing a key immunosurveillance role in early tumor development. Myeloid and NK cells show reciprocal crosstalk, influencing myeloid cell functional status or antigen presentation and NK effector function, respectively. Crosstalk between myeloid cells and the NK immune network in the TME is especially important in the context of therapeutic intervention. Here we discuss how myeloid and NK cell interactions shape anti-tumor responses by influencing an immunosuppressive TME and how this may influence outcomes of treatment strategies involving drugs that target myeloid and NK cells.