Animal hosts harbor diverse assemblages of microbial symbionts that play crucial roles in the host's lifestyle. The link between microbial symbiosis and host development remains poorly understood. In particular, little is known about the adaptive evolution of gut bacteria in host-microbe symbioses. Recently, symbiotic relationships have been categorized as open, closed, or mixed, reflecting their modes of inter-host transmission and resulting in distinct genomic features. Members of the genus Bacteroides are the most abundant human gut microbiota and possess both probiotic and pathogenic potential, providing an excellent model for studying pan-genome evolution in symbiotic systems. Here, we determined the complete genome of an novel clinical strain PL2022, which was isolated from a blood sample and performed pan-genome analyses on a representative set of Bacteroides cellulosilyticus strains to quantify the influence of the symbiotic relationship on the evolutionary dynamics. B. cellulosilyticus exhibited correlated genomic features with both open and closed symbioses, suggesting a mixed symbiosis. An open pan-genome is characterized by abundant accessory gene families, potential horizontal gene transfer (HGT), and diverse mobile genetic elements (MGEs), indicating an innovative gene pool, mainly associated with genomic islands and plasmids. However, massive parallel gene loss, weak purifying selection, and accumulation of positively selected mutations were the main drivers of genome reduction in B. cellulosilyticus. Metagenomic read recruitment analyses showed that B. cellulosilyticus members are globally distributed and active in human gut habitats, in line with predominant vertical transmission in the human gut. However, existence and/or high abundance were also detected in non-intestinal tissues, other animal hosts, and non-host environments, indicating occasional horizontal transmission to new niches, thereby creating arenas for the acquisition of novel genes. This case study of adaptive evolution under a mixed host-microbe symbiosis advances our understanding of symbiotic pan-genome evolution. Our results highlight the complexity of genetic evolution in this unusual intestinal symbiont.