To explain differences in gut microbial communities we must determine how processes regulating microbial community assembly (colonization, persistence) differ among hosts and affect microbiota composition. We surveyed the gut microbiota of threespine stickleback (Gasterosteus aculeatus) from 10 geographically clustered populations and sequenced environmental samples to track potential colonizing microbes and quantify the effects of host environment and genotype. Gut microbiota composition and diversity varied among populations. These among-population differences were associated with multiple covarying ecological variables: habitat type (lake, stream, estuary), lake geomorphology and food- (but not water-) associated microbiota. Fish genotype also covaried with gut microbiota composition; more genetically divergent populations exhibited more divergent gut microbiota. Our results suggest that population level differences in stickleback gut microbiota may depend more on internal sorting processes (host genotype) than on colonization processes (transient environmental effects).