Recurrent aphthous stomatitis (RAS) is the most common disease affecting oral mucosae. Etiology is unknown, but several factors have been implicated, all of which influence the composition of microbiota residing on oral mucosae, which in turn modulates immunity and thereby affects disease progression. Although no individual pathogens have been conclusively shown to be causative agents of RAS, imbalanced composition of the oral microbiota may play a key role. In this study, we sought to determine composition profiles of bacterial microbiota in the oral mucosa associated with RAS. Using high-throughput 16S rRNA gene sequencing, we characterized the most abundant bacterial populations residing on healthy and ulcerated mucosae in patients with RAS (recruited using highly stringent criteria) and no associated medical conditions; we also compared these to the bacterial microbiota of healthy controls (HCs). Phylum-level diversity comparisons revealed decreased Firmicutes and increased Proteobacteria in ulcerated sites, as compared with healthy sites in RAS patients, and no differences between RAS patients with healthy sites and HCs. Genus-level analysis demonstrated higher abundance of total Bacteroidales in RAS patients with healthy sites over HCs. Porphyromonadaceae comprising species associated with periodontal disease and Veillonellaceae predominated in ulcerated sites over HCs, while no quantitative differences of these families were observed between healthy sites in RAS patients and HCs. Streptococcaceae comprising species associated with oral health predominated in HCs over ulcerated sites but not in HCs over healthy sites in RAS patients. This study demonstrates that mucosal microbiome changes in patients with idiopathic RAS-namely, increased Bacteroidales species in mucosae of RAS patients not affected by active ulceration. While these changes suggest a microbial role in initiation of RAS, this study does not provide data on causality. Within this limitation, the study contributes to the understanding of the potential role of mucosal microbiome changes in oral mucosal disease.