Background: We sought to determine whether an extensively hydrolyzed formula (EHF) supplemented with two human milk oligosaccharides (HMO) was tolerated by infants with cow’s milk protein allergy (CMPA). Methods: A whey-based EHF (Test formula) containing 2′fucosyl-lactose (2′FL) and lacto-N-neotetraose (LNnT) was assessed for clinical hypoallergenicity and safety. The Control formula was a currently marketed EHF without HMO. Children with CMPA, aged 2 months to 4 years, were assessed by double-blind, placebo-controlled food challenges (DBPCFC) to both formulas, in randomized order. If both DBPCFC were negative, subjects participated in a one-week, open food challenge (OFC) with the Test formula. Symptoms and adverse events were recorded. Hypoallergenicity was accepted if at least 90% (with 95% confidence intervals) of subjects tolerated the Test formula. Results: Of the 82 children with CMPA that were screened, 67 (intention-to-treat [ITT] cohort—mean age 24.5 ± 13.6 months; range 2–57; 45 [67.2%] male) were randomized to receive either the Test or the Control formula during the first DBPCFC. Of these, 64 children completed at least one DBPCFC (modified intention-to-treat [mITT] cohort). Three children were excluded due to protocol deviations (per protocol [PP] cohort; n = 61). There was one allergic reaction to the Test, and one to the Control formula. On the mITT analysis, 63 out of 64 (98.4%; 95% CI lower bound 92.8%), and on the PP analysis 60 out of 61 (98.4%; 95% CI lower bound 92.5%) participants tolerated the Test formula, confirming hypoallergenicity. Conclusion: The whey-based EHF supplemented with 2′FL and LNnT met the clinical hypoallergenicity criteria and can be recommended for the management of CMPA in infants and young children.