Cow's milk allergy (CMA) continues to be a growing health concern for infants living in Western countries. The long-term prognosis for the majority of affected infants is good, with about 80% naturally acquiring tolerance by the age of four years. However, recent studies suggest that the natural history of CMA is changing, with an increasing persistence until later ages. The pathogenesis of CMA, as well as oral tolerance, is complex and not completely known, although numerous studies implicate gut-associated immunity and enteric microflora, and it has been suggested that an altered composition of intestinal microflora results in an unbalanced local and systemic immune response to food allergens. In addition, there are qualitative and quantitative differences in the composition of gut microbiota between patients affected by CMA and healthy infants. These findings prompt the concept that specific beneficial bacteria from the human intestinal microflora, designated probiotics, could restore intestinal homeostasis and prevent or alleviate allergy, at least in part by interacting with the intestinal immune cells. The aim of this paper is to review what is currently known about the use of probiotics as dietary supplements in CMA.