Growing evidence supports the importance of gut microbiota in the control of tumor growth and response to therapy. Here, we select prebiotics that can enrich bacterial taxa that promote anti-tumor immunity. Addition of the prebiotics inulin or mucin to the diet of C57BL/6 mice induces anti-tumor immune responses and inhibition of BRAF mutant melanoma growth in a subcutaneously implanted syngeneic mouse model. Mucin fails to inhibit tumor growth in germ-free mice, indicating that the gut microbiota is required for the activation of the anti-tumor immune response. Inulin and mucin drive distinct changes in the microbiota, as inulin, but not mucin, limits tumor growth in syngeneic mouse models of colon cancer and NRAS mutant melanoma and enhances the efficacy of a MEK inhibitor against melanoma while delaying the emergence of drug resistance. We highlight the importance of gut microbiota in anti-tumor immunity and the potential therapeutic role for prebiotics in this process.