The microbial ecology of Mycobacterium avium subspecies paratuberculosis infections (MAP) within the context of Multiple Sclerosis (MS) is largely an unexplored topic in the literature. Thus, we have characterized the compositional and predicted functional differences of the gut microbiome between MS patients with MAP (MAP+) and without (MAP−) infection. This was done in the context of exposome differences (through self-reported filled questionnaires), principally in anthropometric and sociodemographic patterns to gain an understanding of the gut microbiome dynamics. 16S rRNA microbiome profiling of faecal samples (n = 69) was performed for four groups, which differed by disease and MAP infection: healthy cohort (HC) MAP−; HC MAP+ ; MS MAP−; and MS MAP+ . Using a dynamic strategy, with MAP infection and time of sampling as occupancy models, we have recovered the core microbiome for both HC and MS individuals. Additional application of neutral modeling suggests key genera that are under selection pressure by the hosts. These include members of the phyla Actinobacteriota, Bacteroidota, and Firmicutes. As several subjects provided multiple samples, a Quasi Conditional Association Test that incorporates paired-nature of samples found major differences in Archaea. To consolidate treatment groups, confounders, microbiome, and the disease outcome parameters, a mediation analysis is performed for MS cohort. This highlighted certain genera i.e., Sutterella, Akkermansia, Bacteriodes, Gastranaerophilales, Alistipes, Balutia, Faecalibacterium, Lachnospiraceae, Anaerostipes, Ruminococcaceae, Eggerthellaceae and Clostridia-UCG-014 having mediatory effect using disease duration as an outcome and MAP infection as a treatment group. Our analyses indicate that the gut microbiome may be an important target for dietary and lifestyle intervention in MS patients with and without MAP infection.