Background Children with medically complicated severe acute malnutrition (SAM) have high risk of inpatient mortality. Diarrhea, carbohydrate malabsorption, and refeeding syndrome may contribute to early mortality and delayed recovery. We tested the hypothesis that a lactose-free, low-carbohydrate F75 milk would serve to limit these risks, thereby reducing the number of days in the stabilization phase. Methods and findings In a multicenter double-blind trial, hospitalized severely malnourished children were randomized to receive standard formula (F75) or isocaloric modified F75 (mF75) without lactose and with reduced carbohydrate. The primary endpoint was time to stabilization, as defined by the World Health Organization (WHO), with intention-to-treat analysis. Secondary outcomes included in-hospital mortality, diarrhea, and biochemical features of malabsorption and refeeding syndrome. The trial was registered at clinicaltrials.gov (NCT02246296). Four hundred eighteen and 425 severely malnourished children were randomized to F75 and mF75, respectively, with 516 (61%) enrolled in Kenya and 327 (39%) in Malawi. Children with a median age of 16 months were enrolled between 4 December 2014 and 24 December 2015. One hundred ninety-four (46%) children assigned to F75 and 188 (44%) to mF75 had diarrhea at admission. Median time to stabilization was 3 days (IQR 2–5 days), which was similar between randomized groups (0.23 [95% CI −0.13 to 0.60], P = 0.59). There was no evidence of effect modification by diarrhea at admission, age, edema, or HIV status. Thirty-six and 39 children died before stabilization in the F75 and in mF75 arm, respectively (P = 0.84). Cumulative days with diarrhea (P = 0.27), enteral (P = 0.42) or intravenous fluids (P = 0.19), other serious adverse events before stabilization, and serum and stool biochemistry at day 3 did not differ between groups. The main limitation was that the primary outcome of clinical stabilization was based on WHO guidelines, comprising clinical evidence of recovery from acute illness as well as metabolic stabilization evidenced by recovery of appetite. Conclusions Empirically treating hospitalized severely malnourished children during the stabilization phase with lactose-free, reduced-carbohydrate milk formula did not improve clinical outcomes. The biochemical analyses suggest that the lactose-free formulae may still exceed a carbohydrate load threshold for intestinal absorption, which may limit their usefulness in the context of complicated SAM.