The tumor immune microenvironment (TIME) has largely been reported to cooperate on tumor onset and progression, as a consequence of the phenotype/functional plasticity and adaptation capabilities of tumor-infiltrating and tumor-associated immune cells. Immune cells within the tumor micro (tissue-local) and macro (peripheral blood) environment closely interact by cell-to-cell contact and/or via soluble factors, also generating a tumor-permissive soil. These dangerous liaisons have been investigated for pillars of tumor immunology, such as tumor associated macrophages and T cell subsets. Here, we reviewed and discussed the contribution of selected innate immunity effector cells, namely neutrophils and natural killer cells, as “soloists” or by their “dangerous liaisons”, in favoring tumor progression by dissecting the cellular and molecular mechanisms involved.