Despite an increasing appreciation of the importance of host-microbe interactions in ecological and evolutionary processes, the factors shaping microbial communities in wild populations remain poorly understood. We therefore exploited a natural experiment provided by two adjacent Antarctic fur seal (Arctocephalus gazella) colonies of high and low social density and combined 16S rRNA metabarcoding with microsatellite profiling of mother-offspring pairs to investigate environmental and genetic influences on skin microbial communities. Seal-associated bacterial communities differed profoundly between the two colonies, despite the host populations themselves being genetically undifferentiated. Consistent with the hypothesis that social stress depresses bacterial diversity, we found that microbial alpha diversity was significantly lower in the high-density colony. Seals from one of the colonies that contained a stream also carried a subset of freshwater-associated bacteria, indicative of an influence of the physical environment. Furthermore, mothers and their offspring shared similar microbial communities, in support of the notion that microbes may facilitate mother-offspring recognition. Finally, a significant negative association was found between bacterial diversity and heterozygosity, a measure of host genetic quality. Our study thus uncovers a complex interplay between environmental and host genetic effects, while also providing empirical support for the leash model of host control, which posits that bacterial communities are driven not only by bottom-up species interactions, but also by top-down host regulation. Taken together, our findings have broad implications for understanding host-microbe interactions as well as prokaryotic diversity in general.