Animal work indicates exposure to air pollutants may alter the composition of the gut microbiota. This study examined relationships between air pollutants and the gut microbiome in young adults residing in Southern California. Our results demonstrate significant associations between exposure to air pollutants and the composition of the gut microbiome using whole-genome sequencing. Higher exposure to 24-hour O₃ was associated with lower Shannon diversity index, higher Bacteroides caecimuris, and multiple gene pathways, including L-ornithine de novo biosynthesis as well as pantothenate and coenzyme A biosynthesis I. Among other pollutants, higher NO₂ exposure was associated with fewer taxa, including higher Firmicutes. The percent variation in gut bacterial composition that was explained by air pollution exposure was up to 11.2% for O₃ concentrations, which is large compared to the effect size for many other covariates reported in healthy populations. This study provides the first evidence of significant associations between exposure to air pollutants and the compositional and functional profile of the human gut microbiome. These results identify O₃ as an important pollutant that may alter the human gut microbiome.