Background: Phenylketonuria (PKU) is a metabolic disorder that necessitates dietary restrictions, potentially impacting the composition of gut and oral microbiota. This study aimed to compare the microbiota composition between children with PKU and healthy controls. Methods: Using 16S rRNA gene sequencing, we analysed microbial communities at six phylogenetic levels. Results: Our findings revealed significant differences in the gut microbiota: Euryarchaeota was more abundant in controls (p = 0.01), while Bacilli and Lactobacillales were higher in PKU children (p = 0.019). Methanobacteriales were significantly elevated in controls (p = 0.01). At the genus and species levels, PKU children had higher Streptococcus and Eubacterium dolichum (p = 0.019, p = 0.015), whereas controls had more Barnesiella, Coprococcus, and Faecalibacterium prausnitzii (p = 0.014, p = 0.019, p = 0.014). In the oral microbiota, control children exhibited significantly higher Bacteroidetes (p = 0.032), while PKU children had increased Bacilli and Betaproteobacteria (p = 0.0079, p = 0.016). Streptococcus and Neisseria were more prevalent in PKU (p = 0.0079, p = 0.016). Conclusions: These results suggest that PKU and its dietary management significantly alter the gut and oral microbiota composition. Understanding these microbial shifts could have implications for managing PKU and improving patient outcomes.