Background/Objectives: The prevalence of food allergy (FA) in children is increasing. Dysbiosis of the microbiome has been linked to FA but needs to be better understood. We aimed to characterize the gut and skin microbiome of young food-allergic children over time and within different types of immunoglobulin E (IgE)-mediated FA. Methods: We studied 23 patients, as a pilot study of an ongoing prospective multicenter cohort study including children < 2y with newly diagnosed IgE-mediated FA. Samples (feces/skin swabs) were collected at enrollment and at 1-year follow-up and sequenced for the bacterial 16S rRNA gene (hypervariable v1–v2 region). Results: Gut and skin bacterial diversity was significantly higher in patients compared with controls and increased over time (beta test, Shannon diversity, p < 0.01). Within different types of IgE-mediated FA, bacterial diversity was similar. Community composition differed significantly over time and within IgE-mediated FA types (PERMANOVA: p < 0.01). Several significantly different genus abundances were revealed. We observed a positive correlation between high total IgE and a high abundance of the genus Collinsella in patients with a higher number of allergies/sensitizations (≥3), and patients with tree nut and/or peanut allergy. Conclusions: This study revealed an increased bacterial diversity in children with FA compared with non-atopic children. Importantly, the gut and skin microbiome differed in their composition over time and within different types of IgE-mediated FA. These findings contribute to the understanding of microbiome changes in children with FA and indicate the potential of the genus Collinsella as a biomarker for tree nut and/or peanut allergy and possibly for allergy persistence.