The gut microbiota is a complex community of microbial species inhabiting the digestive tract. Each microbial species is further composed of microbes with slightly different genetic variants also known as strains. While most evolutionary studies of the gut microbiome occur at the community-level or focused on narrow clades of vertebrates, few studies have examined the evolution of wildlife and their gut microbiome at the strain-level across the animal kingdom. In this exploratory study, we examine a wildlife gut metagenomic dataset to investigate the evolutionary dynamics of bacterial species and their respective host. In particular, this is the first examination of whether there is significant congruence between the phylogeny of bacterial strains and that of their respective hosts, which we refer to as strain phylosymbiosis, across the animal kingdom. Our analysis of the most abundant bacteria in our dataset revealed Akkermansia muciniphila and Bacteroides vulgatus exhibited strong signals of strain phylosymbiosis.