Growing evidence suggests that the gut microbiome (GM) plays a critical role in health and disease. However, the contribution of GM to psychiatric disorders, especially anxiety, remains unclear. We used the Collaborative Cross (CC) mouse population-based model to identify anxiety associated host genetic and GM factors. Anxiety-like behavior of 445 mice across 30 CC strains was measured using the light/dark box assay and documented by video. A custom tracking system was developed to quantify seven anxiety-related phenotypes based on video. Mice were assigned to a low or high anxiety group by consensus clustering using seven anxiety-related phenotypes. Genome-wide association analysis (GWAS) identified 141 genes (264 SNPs) significantly enriched for anxiety and depression related functions. In the same CC cohort, we measured GM composition and identified five families that differ between high and low anxiety mice. Anxiety level was predicted with 79% accuracy and an AUC of 0.81. Mediation analyses revealed that the genetic contribution to anxiety was partially mediated by the GM. Our findings indicate that GM partially mediates and coordinates the effects of genetics on anxiety.