Understanding the evolutionary relationships between a host and its intestinal resident bacteria can transform how we understand adaptive phenotypic traits. The interplay between hosts and their resident bacteria inevitably affects the intestinal environment and, thereby, the living conditions of both the host and the microbiota. Thereby this co-existence likely influences the fitness of both bacteria and host. Whether this co-existence leads to evolutionary co-diversification in animals is largely unexplored, mainly due to the complexity of the environment and microbial communities and the often low host selection. We present the gut metagenome from wild Atlantic salmon (Salmo salar), a new wild organism model with an intestinal microbiota of low complexity and a well-described population structure, making it well-suited for investigating co-evolution. Our data reveal a strong host selection of a core gut microbiota dominated by a single Mycoplasma species. We found a clear co-diversification between the population structure of Atlantic salmon and nucleotide variability of the intestinal Mycoplasma populations conforming to expectations from co-evolution between host and resident bacteria. Our results show that the stable microbiota of Atlantic salmon has evolved with its salmonid host populations while potentially providing adaptive traits to the salmon host populations, including defence mechanisms, biosynthesis of essential amino acids, and metabolism of B vitamins. We highlight Atlantic salmon as a novel model for studying co-evolution between vertebrate hosts and their resident bacteria. [Figure not available: see fulltext.].