Cancer stem cells (CSCs), also known as tumor-initiating cells, are characterized by an increased capacity for self-renewal, multipotency, and tumor initiation. While CSCs represent only a small proportion of the tumor mass, they significantly account for metastatic dissemination and tumor recurrence, thus making them attractive targets for therapy. Due to their ability to sustain in dormancy, chemo- and radiotherapy often fail to eliminate cancer cells with stemness properties. Recent advances in the understanding of the tumor microenvironment (TME) illustrated the importance of the immune contexture, determining the response to therapy and clinical outcome of patients. In this context, CSCs exhibit special properties to escape the recognition by innate and adaptive immunity and shape the TME into an immunosuppressive, pro-tumorigenic landscape. As CSCs sculpt the immune contexture, the phenotype and functional properties of the tumor-infiltrating immune cells in turn influence the differentiation and phenotype of tumor cells. In this review, we summarize recent studies investigating main immunomodulatory properties of CSCs and their underlying molecular mechanisms as well as the impact of immune cells on cancer cells with stemness properties. A deeper understanding of this bidirectional crosstalk shaping the immunological landscape and determining therapeutic responses will facilitate the improvement of current treatment modalities and the design of innovative strategies to precisely target CSCs.