The interaction between genetic susceptibility, epigenetic, endogenous, and environmental factors play a key role in the initiation and progression of autoimmune thyroid diseases (AITDs). Studies have shown that gut microbiota alterations take part in the development of autoimmune diseases. We have investigated the possible relationship between gut microbiota composition and the most frequent AITDs. A total of nine Hashimoto’s thyroiditis (HT), nine Graves–Basedow’s disease (GD), and 11 otherwise healthy donors (HDs) were evaluated. 16S rRNA pyrosequencing and bioinformatics analysis by Quantitative Insights into Microbial Ecology and Phylogenetic Investigation of Communities by Reconstruction of Unobserved States (PICRUSt) were used to analyze the gut microbiota. Beta diversity analysis showed that gut microbiota from our groups was different. We observed an increase in bacterial richness in HT and a lower evenness in GD in comparison to the HDs. GD showed a significant increase of Fusobacteriaceae, Fusobacterium and Sutterella compared to HDs and the core microbiome features showed that Prevotellaceae and Prevotella characterized this group. Victivallaceae was increased in HT and was part of their core microbiome. Streptococcaceae, Streptococcus and Rikenellaceae were greater in HT compared to GD. Core microbiome features of HT were represented by Streptococcus, Alistipes, Anaerostipes, Dorea and Haemophilus. Faecalibacterium decreased in both AITDs compared to HDs. PICRUSt analysis demonstrated enrichment in the xenobiotics degradation, metabolism, and the metabolism of cofactors and vitamins in GD patients compared to HDs. Moreover, correlation studies showed that some bacteria were widely correlated with autoimmunity parameters. A prediction model evaluated a possible relationship between predominant concrete bacteria such as an unclassified genus of Ruminococcaceae, Sutterella and Faecalibacterium in AITDs. AITD patients present altered gut microbiota compared to HDs. These alterations could be related to the immune system development in AITD patients and the loss of tolerance to self-antigens.