Background: Multiple sclerosis is a chronic immune-mediated disease of the brain and spinal cord resulting in physical and cognitive impairment in young adults. It is hypothesized that a disrupted bacterial and viral gut microbiota is a part of the pathogenesis mediating disease impact through an altered gut microbiota-brain axis. The aim of this study is to explore the characteristics of gut microbiota in multiple sclerosis and to associate it with disease variables, as the etiology of the disease remains only partially known. Methods: Here, in a case-control setting involving 148 Danish cases with multiple sclerosis and 148 matched healthy control subjects, we performed shotgun sequencing of fecal microbial DNA and associated bacterial and viral microbiota findings with plasma cytokines, blood cell gene expression profiles, and disease activity. Results: We found 61 bacterial species that were differentially abundant when comparing all multiple sclerosis cases with healthy controls, among which 31 species were enriched in cases. A cluster of inflammation markers composed of blood leukocytes, CRP, and blood cell gene expression of IL17A and IL6 was positively associated with a cluster of multiple sclerosis-related species. Bacterial species that were more abundant in cases with disease-active treatment-naïve multiple sclerosis were positively linked to a group of plasma cytokines including IL-22, IL-17A, IFN-β, IL-33, and TNF-α. The bacterial species richness of treatment-naïve multiple sclerosis cases was associated with number of relapses over a follow-up period of 2 years. However, in non-disease-active cases, we identified two bacterial species, Faecalibacterium prausnitzii and Gordonibacter urolithinfaciens, whose absolute abundance was enriched. These bacteria are known to produce anti-inflammatory metabolites including butyrate and urolithin. In addition, cases with multiple sclerosis had a higher viral species diversity and a higher abundance of Caudovirales bacteriophages. Conclusions: Considerable aberrations are present in the gut microbiota of patients with multiple sclerosis that are directly associated with blood biomarkers of inflammation, and in treatment-naïve cases bacterial richness is positively associated with disease activity. Yet, the finding of two symbiotic bacterial species in non-disease-active cases that produce favorable immune-modulating compounds provides a rationale for testing these bacteria as adjunct therapeutics in future clinical trials.