The commensal microbiota has been implicated in the regulation of a diverse array of physiological processes, both within the gastrointestinal tract and at distant tissue sites. Cancer is no exception, and distinct aspects of the microbiota have been reported to have either pro- or anti-tumor effects. The functional role of the microbiota in regulating not only mucosal but also systemic immune responses has led to investigations into the impact on cancer immunotherapies, particularly with agents targeting the immunologic checkpoints PD-1 and CTLA-4. Microbial sequencing and reconstitution of germ-free mice have indicated both positive and negative regulatory bacteria likely exist, which either promote or interfere with immunotherapy efficacy. These collective findings have led to the development of clinical trials pursuing microbiome-based therapeutic interventions, with the hope of expanding immunotherapy efficacy. This review summarizes recent knowledge about the relationship between the host microbiota and cancer and anti-tumor immune response, with implications for cancer therapy.