The pathogenesis of multiple sclerosis (MS), an autoimmune disease affecting the brain and spinal cord, remains poorly understood. Patients with MS typically present with recurrent episodes of neurological dysfunctions such as blindness, paresis, and sensory disturbances. Studies on experimental autoimmune encephalomyelitis (EAE) animal models have led to a number of testable hypotheses including a hypothetical role of altered gut microbiota in the development of MS. To investigate whether gut microbiota in patients with MS is altered, we compared the gut microbiota of 20 Japanese patients with relapsing-remitting (RR) MS (MS20) with that of 40 healthy Japanese subjects (HC40) and an additional 18 healthy subjects (HC18). All the HC18 subjects repeatedly provided fecal samples over the course of months (158 samples in total). Analysis of the bacterial 16S ribosomal RNA (rRNA) gene by using a high-throughput culture-independent pyrosequencing method provided evidence of a moderate dysbiosis in the structure of gut microbiota in patients with MS. Furthermore, we found 21 species that showed significant differences in relative abundance between the MS20 and HC40 samples. On comparing MS samples to the 158 longitudinal HC18 samples, the differences were found to be reproducibly significant for most of the species. These taxa comprised primarily of clostridial species belonging to Clostridia clusters XIVa and IV and Bacteroidetes. The phylogenetic tree analysis revealed that none of the clostridial species that were significantly reduced in the gut microbiota of patients with MS overlapped with other spore-forming clostridial species capable of inducing colonic regulatory T cells (Treg), which prevent autoimmunity and allergies; this suggests that many of the clostridial species associated with MS might be distinct from those broadly associated with autoimmune conditions. Correcting the dysbiosis and altered gut microbiota might deserve consideration as a potential strategy for the prevention and treatment of MS.