Cow's milk protein allergy (CMPA) is best treated by complete elimination of cow's milk from the diet. For infants with CMPA who cannot be breast-fed, formulas based on extensively hydrolyzed proteins or on amino acids are the preferred substitutes for cow's milk-based formulas. In this study, we compared the tolerance and growth of infants with CMPA who were fed a new extensively hydrolyzed formula containing lactose (eHF) with those who were fed an amino acid formula (AAF). This was a prospective, multi-center, randomized, reference-controlled study. Seventy-seven infants <12 months old with suspected CMPA were enrolled. In 66 of these, CMPA was confirmed by oral challenge in a double-blind, placebo-controlled food challenge (DBPCFC) or by a medical history of severe allergic reaction to cow's milk and a positive skin prick test. These infants were then tested for their reaction to eHF and AAF in a DBPCFC. All infants tolerated both formulas and were randomized to receive either eHF (n = 34) or AAF (n = 32) for 180 days. Growth (weight, length, and head circumference) and tolerance [skin, gastro-intestinal, and respiratory tract symptoms of allergy] were evaluated after 30, 60, 90, and 180 days. There were no significant differences between the two groups in any of the growth measurements. Length and head circumference were similar to Euro-growth standards, but weight was slightly lower. Gastro-intestinal and respiratory tract symptoms of allergy were also similar in the two groups. However, whereas SCORAD scores for atopic dermatitis remained constant throughout the study in infants-fed eHF, there was a slight decrease in those fed AAF. Infants-fed eHF had significantly fewer incidents of vomiting than infants-fed AAF and a significantly higher frequency of soft stools. The new eHF is safe and well tolerated in infants diagnosed with CMPA.