A large body of data both in animals and humans demonstrates that the gut microbiome plays a fundamental role in cancer immunity and in determining the efficacy of cancer immunotherapy. In this work, we have investigated whether and to what extent the gut microbiome can influence the antitumor activity of neo-epitope-based cancer vaccines in a BALB/c-CT26 cancer mouse model. Similarly to that observed in the C57BL/6-B16 model, Bifidobacterium administration per se has a beneficial effect on CT26 tumor inhibition. Furthermore, the combination of Bifidobacterium administration and vaccination resulted in a protection which was superior to vaccination alone and to Bifidobacterium administration alone, and correlated with an increase in the frequency of vaccine-specific T cells. The gut microbiome analysis by 16S rRNA gene sequencing and shotgun metagenomics showed that tumor challenge rapidly altered the microbiome population, with Muribaculaceae being enriched and Lachnospiraceae being reduced. Over time, the population of Muribaculaceae progressively reduced while the Lachnospiraceae population increased—a trend that appeared to be retarded by the oral administration of Bifidobacterium. Interestingly, in some Bacteroidales, Prevotella and Muribaculacee species we identified sequences highly homologous to immunogenic neo-epitopes of CT26 cells, supporting the possible role of “molecular mimicry” in anticancer immunity. Our data strengthen the importance of the microbiome in cancer immunity and suggests a microbiome-based strategy to potentiate neo-epitope-based cancer vaccines.