Increasing evidence suggests that perturbations in the intestinal microbiota composition of infants are implicated in the pathogenesis of food allergy (FA), while the actual structure and composition of the intestinal microbiota in human beings with FA remain unclear. Microbial diversity and composition were analyzed with parallel barcoded 454 pyrosequencing targeting the 16S rRNA gene hypervariable V1-V3 regions in the feces of 34 infants with FA (17 IgE mediated and 17 non-IgE mediated) and 45 healthy controls. Here, we showed that several key FA-associated bacterial phylotypes, but not the overall microbiota diversity, significantly changed in infancy fecal microbiota with FA and were associated with the development of FA. The proportion of abundant Bacteroidetes, Proteobacteria, and Actinobacteria phyla were significantly reduced, while the Firmicutes phylum was highly enriched in the FA group (P < 0.05). Abundant Clostridiaceae 1 organisms were prevalent in infants with FA at the family level (P = 0.016). FA-enriched phylotypes negatively correlated with interleukin-10, for example, the genera Enterococcus and Staphylococcus. Despite profound interindividual variability, levels of 20 predominant genera were significantly different between the FA and healthy control groups (P < 0.05). Infants with IgE-mediated FA had increased levels of Clostridium sensu stricto and Anaerobacter and decreased levels of Bacteroides and Clostridium XVIII (P < 0.05). A positive correlation was observed between Clostridium sensu stricto and serum-specific IgE (R = 0.655, P < 0.001). The specific microbiota signature could distinguish infants with IgE-mediated FA from non-IgE-mediated ones. Detailed microbiota analysis of a well-characterized cohort of infants with FA showed that dysbiosis of fecal microbiota with several FA-associated key phylotypes may play a pathogenic role in FA.