Novel immunotherapy approaches have provided durable remission in a significant number of cancer patients with cancers previously considered rapidly lethal. Nonetheless, the high degree of nonresponders, and in some cases the emergence of resistance in patients who do initially respond, represents a significant challenge in the field of cancer immunotherapy. These issues prompt much more extensive studies to better understand how cancer cells escape immune surveillance and resist immune attacks. Here, we review the current knowledge of how cellular heterogeneity and plasticity could be involved in shaping the tumor microenvironment (TME) and in controlling antitumor immunity. Indeed, recent findings have led to increased interest in the mechanisms by which cancer cells undergoing epithelial-mesenchymal transition (EMT), or oscillating within the EMT spectrum, might contribute to immune escape through multiple routes. This includes shaping of the TME and decreased susceptibility to immune effector cells. Although much remains to be learned on the mechanisms at play, cancer cell clones with mesenchymal features emerging from the TME seem to be primed to face immune attacks by specialized killer cells of the immune system, the natural killer cells, and the cytotoxic T lymphocytes. Recent studies investigating patient tumors have suggested EMT as a candidate predictive marker to be explored for immunotherapy outcome. Promising data also exist on the potential utility of targeting these cancer cell populations to at least partly overcome such resistance. Research is now underway which may lead to considerable progress in optimization of treatments.