Vaccines are one of the greatest successes of public health, preventing millions of cases of disease and death in children each year. However, the efficacy of many vaccines can vary greatly between infants from geographically and socioeconomically distinct locations. Differences in the composition of the intestinal microbiome have emerged as one of the main factors that can account for variations in immunisation outcomes. In this Review, we assess the influence of the gut microbiota upon early life immunity, focusing on two important members of the microbiota with health-promoting and immunomodulatory properties: Bifidobacterium and Bacteroides. Additionally, we discuss their immune stimulatory microbial properties, interactions with the host, and their effect on vaccine responses and efficacy in infants. We also provide an overview of current microbiota-based approaches to enhance vaccine outcomes, and describe novel microbe-derived components that could lead to safer, more effective vaccines and vaccine adjuvants.