The persistence and intimacy of mammalian host-microbe interactions over evolutionary timescales is controversial. This is partly because host phylogeny and diet are so deeply confounded that it may not be possible to disentangle their individual contributions to microbiome evolution. Here, we show that host phylogeny and diet influence the distribution of independent gut bacterial lineages, and do so on vastly different timescales. Diet mostly influences the acquisition of deeply divergent (>300 Ma) microbial lineages, while associations with host phylogeny are seen across more recent lineages. Considering microbiome at appropriate phylogenetic scales allows us to model the evolution of the microbiome along the mammalian tree, and to accurately infer ancient diets from the predicted microbiomes of mammalian ancestors. More detailed phylogenetic analysis reveals for the first time, large-scale patterns of co-speciation between mammals and their gut symbionts, some of which are associated with immune diseases in humans. Surprisingly, the bacterial genera with the greatest amounts of co-speciation with their hosts have been widely overlooked in previous studies, laying a path for future studies that probe these newly discovered host-microbe associations for signs of co-evolution.