Accumulating evidence points to an important role for the gut microbiome in anti-tumor immunity. Here, we show that altered intestinal microbiota contributes to anti-tumor immunity, limiting tumor expansion. Mice lacking the ubiquitin ligase RNF5 exhibit attenuated activation of the unfolded protein response (UPR) components, which coincides with increased expression of inflammasome components, recruitment and activation of dendritic cells and reduced expression of antimicrobial peptides in intestinal epithelial cells. Reduced UPR expression is also seen in murine and human melanoma tumor specimens that responded to immune checkpoint therapy. Co-housing of Rnf5^-/- and WT mice abolishes the anti-tumor immunity and tumor inhibition phenotype, whereas transfer of 11 bacterial strains, including B. rodentium, enriched in Rnf5^-/- mice, establishes anti-tumor immunity and restricts melanoma growth in germ-free WT mice. Altered UPR signaling, exemplified in Rnf5^-/- mice, coincides with altered gut microbiota composition and anti-tumor immunity to control melanoma growth.