Food allergy (FA) and, in particular, IgE-mediated cow’s milk allergy is associated with compositional and functional changes of gut microbiota. In this study, we compared the gut microbiota of cow’s milk allergic (CMA) infants with that of cow’s milk sensitized (CMS) infants and Healthy controls. The effect of the intake of a mixture of Bifidobacterium longum subsp. longum BB536, Bifidobacterium breve M-16V and Bifidobacterium longum subsp. infantis M-63 on gut microbiota modulation of CMA infants and probiotic persistence was also investigated. Gut microbiota of CMA infants resulted to be characterized by a dysbiotic status with a prevalence of some bacteria as Haemophilus, Klebsiella, Prevotella, Actinobacillus and Streptococcus. Among the three strains administered, B.longum subsp. infantis colonized the gastrointestinal tract and persisted in the gut microbiota of infants with CMA for 60 days. This colonization was associated with perturbations of the gut microbiota, specifically with the increase of Akkermansia and Ruminococcus. Multi-strain probiotic formulations can be studied for their persistence in the intestine by monitoring specific bacterial probes persistence and exploiting microbiota profiling modulation before the evaluation of their therapeutic effects.