Endometriosis remains a challenge to understand and to diagnose. This is an observational cross-sectional pilot study to characterize the gut and vaginal microbiome profiles among endometriosis patients and control subjects without the disease and to explore their potential use as a less-invasive diagnostic tool for endometriosis. Overall, 59 women were included, n?=?35 with endometriosis and n?=?24 controls. Rectal and vaginal samples were collected in two different periods of the menstrual cycle from all subjects. Gut and vaginal microbiomes from patients with different rASRM (revised American Society for Reproductive Medicine) endometriosis stages and controls were analyzed. Illumina sequencing libraries were constructed using a two-step 16S rRNA gene PCR amplicon approach. Correlations of 16S rRNA gene amplicon data with clinical metadata were conducted using a random forest-based machine-learning classification analysis. Distribution of vaginal CSTs (community state types) significantly differed between follicular and menstrual phases of the menstrual cycle (p?=?0.021, Fisher's exact test). Vaginal and rectal microbiome profiles and their association to severity of endometriosis (according to rASRM stages) were evaluated. Classification models built with machine-learning methods on the microbiota composition during follicular and menstrual phases of the cycle were built, and it was possible to accurately predict rASRM stages 1-2 verses rASRM stages 3-4 endometriosis. The feature contributing the most to this prediction was an OTU (operational taxonomic unit) from the genus Anaerococcus. Gut and vaginal microbiomes of women with endometriosis have been investigated. Our findings suggest for the first time that vaginal microbiome may predict stage of disease when endometriosis is present.