: Undernutrition is a major public health challenge in Mozambique, requiring a better understanding of changes in weight and body composition. In the present study, changes in weight and body composition were analyzed in undernourished children, and predictors of these changes were identified during and after hospitalization. A longitudinal cohort study was conducted in Maputo, Mozambique (2018–2020), in children aged 6 to 58 months hospitalized for malnutrition. On hospital admission, clinical data, including anemia, edema, and HIV infection status, were collected. Anthropometric measurements, height, weight, and skinfold thickness, were obtained during hospital and community follow-ups. Stool samples were collected to assess intestinal parasitic infections. Longitudinal linear mixed-effects models were used to identify factors associated with changes in weight and proxies of body composition (sum of skinfolds and percentage body fat [%BF]) over time. A total of 217 children were included, with a mean age of 19.2 ± 8.4 months. On admission, 43.7% (94/215) of patients had kwashiorkor, 88.7% (188/212) had anemia, and 55.8% (121/217) had edema. HIV infection was diagnosed in 25.7% (55/214) of patients, and 26.7% (58/217) were positive for intestinal parasitic infections. HIV infection was a strong predictor associated with lower weight gain and body composition change over time (sum of skinfold and estimated %BF), whereas edema was associated with increased gains ( P <0.001). Intestinal parasitic infections were associated with weight changes only in univariate analysis ( P <0.05). HIV infection and edema at admission were major determinants of recovery, emphasizing targeted HIV care and continued edema monitoring.