Phenylketonuria (PKU) is an inborn error of metabolism associated with high blood levels of phenylalanine (Phe). A Phe-restricted diet supplemented with L-amino acids is the main treatment strategy for this disease; if started early, most neurological abnormalities can be prevented. The healthy human gut contains trillions of commensal bacteria, often referred to as the gut microbiota. The composition of the gut microbiota is known to be modulated by environmental factors, including diet. In this study, we compared the gut microbiota of 8 PKU patients on Phe-restricted dietary treatment with that of 10 healthy individuals. The microbiota were characterized by 16S rRNA sequencing using the Ion Torrent™ platform. The most dominant phyla detected in both groups were Bacteroidetes and Firmicutes. PKU patients showed reduced abundance of the Clostridiaceae, Erysipelotrichaceae, and Lachnospiraceae families, Clostridiales class, Coprococcus, Dorea, Lachnospira, Odoribacter, Ruminococcus and Veillonella genera, and enrichment of Prevotella, Akkermansia, and Peptostreptococcaceae. Microbial function prediction suggested significant differences in starch/glucose and amino acid metabolism between PKU patients and controls. Together, our results suggest the presence of distinct taxonomic groups within the gut microbiome of PKU patients, which may be modulated by their plasma Phe concentration. Whether our findings represent an effect of the disease itself, or a consequence of the modified diet is unclear.