Although the intestinal microbiome has been increasingly implicated in autoimmune diseases, much is unknown about its roles in Multiple Sclerosis (MS). Our aim was to compare the microbiome between treatment-naïve MS subjects early in their disease course and controls, and between Caucasian (CA), Hispanic (HA), and African American (AA) MS subjects. From fecal samples, we performed 16S rRNA V4 sequencing and analysis from 45 MS subjects (15 CA, 16 HA, 14 AA) and 44 matched healthy controls, and whole metagenomic shotgun sequencing from 24 MS subjects (all newly diagnosed, treatment-naïve, and steroid-free) and 24 controls. In all three ethnic groups, there was an increased relative abundance of the same single genus, Clostridium, compared to ethnicity-matched controls. Analysis of microbiota networks showed significant changes in the network characteristics between combined MS cohorts and controls, suggesting global differences not restricted to individual taxa. Metagenomic analysis revealed significant enrichment of individual species within Clostridia as well as particular functional pathways in the MS subjects. The increased relative abundance of Clostridia in all three early MS cohorts compared to controls provides candidate taxa for further study as biomarkers or as etiologic agents in MS.