T cell infiltration of solid tumors is associated with favorable patient outcomes, yet the mechanisms underlying variable immune responses between individuals are not well understood. One possible modulator could be the intestinal microbiota. We compared melanoma growth in mice harboring distinct commensal microbiota and observed differences in spontaneous antitumor immunity, which were eliminated upon cohousing or following fecal transfer. 16S ribosomal RNA sequencing identified Bifidobacterium as associated with the antitumor effects. Oral administration of Bifidobacterium alone improved tumor control to the same degree as anti–PD-L1 therapy (checkpoint blockade), and combination treatment nearly abolished tumor outgrowth. Augmented dendritic cell function leading to enhanced CD8+ T cell priming and accumulation in the tumor microenvironment mediated the effect. Our data suggest that manipulating the microbiota may modulate cancer immunotherapy.