Gut microbial composition depends on different dietary habits just as health depends on microbial metabolism, but the association of microbiota with different diets in human populations has not yet been shown. In this work, we compared the fecal microbiota of European children (EU) and that of children from a rural African village of Burkina Faso (BF), where the diet, high in fiber content, is similar to that of early human settlements at the time of the birth of agriculture. By using high-throughput 16S rDNA sequencing and biochemical analyses, we found significant differences in gut microbiota between the two groups. BF children showed a significant enrichment in Bacteroidetes and depletion in Firmicutes (P < 0.001), with a unique abundance of bacteria from the genus Prevotella and Xylanibacter, known to contain a set of bacterial genes for cellulose and xylan hydrolysis, completely lacking in the EU children. In addition, we found significantly more short-chain fatty acids (P < 0.001) in BF than in EU children. Also, Enterobacteriaceae (Shigella and Escherichia) were significantly underrepresented in BF than in EU children (P < 0.05). We hypothesize that gut microbiota coevolved with the polysaccharide-rich diet of BF individuals, allowing them to maximize energy intake from fibers while also protecting them from inflammations and noninfectious colonic diseases. This study investigates and compares human intestinal microbiota from children characterized by a modern western diet and a rural diet, indicating the importance of preserving this treasure of microbial diversity from ancient rural communities worldwide.