Myeloid cells are effectors of both anti-tumor and pro-tumor immune responses, but much needs to be determined as to signals that determine which function of the myeloid lineage dominates. Shown here, mice with myeloid-specific IKKβ loss exhibit more rapid growth of cutaneous and lung melanoma tumors. Specifically, in a BRAF(V600E)PTEN-/- allograft model, IKKβ loss in macrophages resulted in reduced recruitment of myeloid cells into the tumor, reduced expression of MHCII, and enhanced production of the chemokine, CCL11, which negatively regulated dendritic cell maturation. The elevated serum and tissue levels of CCL11 mediated suppression of dendritic cell differentiation/maturation within the TME, resulted in a Th2 skew of the immune response, and impaired CD8+T cell-mediated tumor cell killing. Macrophage depletion or CD8+T cell depletion in mice with IKKβWT myeloid cells enhanced tumor growth in the melanoma allograft. In contrast, mice with IKKβWT myeloid cells used the myeloid cell response to mediate anti-tumor immunity against the syngeneic B16 melanoma, with less apparent dependency on a CD8+T cell response. Myeloid cells deficient in IKKβ were compromised in tumor cell killing based upon reduced ability to phagocytize and digest tumor cells. Conversely, mice with continuous IKKβ signaling in myeloid-lineage cells (IKKβCA) exhibited enhanced anti-tumor immunity and reduced B16 melanoma tumor growth. Collectively, these data uncover new mechanisms by which NF-κB signaling in myeloid cells promotes innate tumor surveillance.