Associations between eukaryotic organisms and microbial symbionts contribute to a diversity of host functions, including growth and immune system development. Despite these broad effects of the microbiome on host function, the mechanisms linking host processes and microbiome composition are still being elucidated. Using a model teleost species, Gasterosteus aculeatus (three-spined stickleback), we investigated patterns of co-variation between gut microbiome composition and host gene expression, focusing specifically on immune-related processes. First, we tested hypotheses of co-variation between microbiome diversity and expression of immune-related genes, and found strong positive associations between microbial alpha diversity and immune gene expression. Next we examined correlations between abundance of specific microbial taxa and gene expression. We identified 15 microbial families that were highly correlated with approximately 1200 host genes. These 15 families fell into three categories: those positively correlated, negatively correlated, and neutrally related to immune processes. Positively immune-correlated families included unclassified Firmicutes, while negatively immune-correlated families included many families within the phylum Proteobacteria. Increased functional understanding of these specific families will help disentangle mechanisms of correlation between microbial families and host immune processes. This is, to our knowledge, the first comprehensive study of co-variation between gut microbiome composition and host gene expression. Our data supports predominate hypotheses of an intimate link between gut microbial composition and host immune function.