The adaptive immune system plays a crucial role in anti-tumor surveillance. Enhancement of T cell responses through checkpoint blockade has become a major therapeutic avenue of intervention for several tumors. Because it shapes immune responses and regulates their amplitude and duration, the microbiota has a substantial impact on anti-tumor immunity. Innate lymphoid cells (ILCs) comprise a heterogeneous population of lymphocytes devoid of antigen-specific receptors that mirror T helper cells in their ability to secrete cytokines that activate immune responses. Ongoing studies suggest that ILCs contribute to anti-tumor responses. Moreover, since ILCs are present at barrier surfaces, they are stimulated by the microbiota and, reciprocally, influence the composition of the microbiota by regulating the surface barrier microenvironment. Thus, ILC-microbiota cross-talk may in part underpin the effects of the microbiota on anti-tumor responses. In this article, we review current evidence linking ILCs to cancer and discuss the potential impact of ILC-microbiota cross-talk in anti-tumor immune responses.