Malnutrition is still a major public health issue in sub-Saharan Africa and Mozambique. The main aim of this study was to evaluate the adherence to the nutritional rehabilitation program (NRP) and its impact on the growth of malnourished children in Beira, Mozambique. The secondary aim was to verify the prevalence of HIV infection in malnourished children at the time of admission to the NRP. A retrospective observational study in Beira Central Hospital and 10 health centers in Beira, Mozambique, was conducted. All children 0 to 5 years of age with acute malnutrition admitted to the outpatient services of the NRP from March 2016 until February 2017 were included in the study. A total of 1,231 children with the following characteristics have been enrolled: 58% female; 33% severely malnourished; and 16.5% HIV-positive. Of the 198 (21.7%) children who completed the program, 177 (89.4%) recovered from malnutrition and 21 (10.6%) did not. Ten (1.1%) were hospitalized and 706 (77.2%) dropped out of the program. Among children who completed the program, the median weight-for-length and weight-for-height z-scores at admission were ≥ -3 and < -2; at discharge, these median z-scores were ≥ -1 (P < 0.001). Children with HIV infection and who were male had a higher prevalence of severe acute malnutrition (P < 0.001). Weight gain was found to be significant after 23 days (P = 0.004) of consuming supplements (ready-to-use therapeutic food). A diagnosis of the degree of malnutrition was accurate at admission for 70.5%; at discharge, this diagnosis was accurate for 67.2%. The NRP seems to be successful if correctly followed, even if it is limited by adherence problems. However, its effectiveness requires further investigation.