Undernutrition among children under five remains a major public health problem in Indonesia, particularly in East Nusa Tenggara Province. According to the 2024 Health Profile of East Nusa Tenggara Province, the prevalence of undernourished (wasted) children in South Central Timor Regency increased from 5.1% in 2019–2020 to 9.7% in 2024, indicating a persistent burden of acute malnutrition. While plant-based, nutrient-dense foods such as Moringa oleifera leaf powder have been widely promoted, evidence on their effectiveness when combined with high–biological-value animal protein, particularly eggs, remains limited. This study aimed to assess the effect of combined moringa leaf powder and egg supplementation on appetite and nutritional status among undernourished children aged 36–59 months. A quasi-experimental study with a control group was conducted from May to July 2025 in the Batuputih Health Center area. Forty undernourished children (weight-for-age Z-score −3 to −2 SD) were allocated to an intervention group (15 g/day moringa leaf powder plus one egg) or a control group (one egg only) for 60 days. Appetite was assessed using the Children’s Eating Behaviour Questionnaire (CEBQ), and nutritional status was evaluated using WHO anthropometric indices Significant improvements in weight-for-age and weight-for-height were observed in both groups (p < 0.05). However, a significant increase in appetite was found only in the intervention group (p = 0.039), while no significant change was observed in height-for-age. The integration of moringa leaf powder with egg-based animal protein effectively improves appetite and short-term nutritional status, supporting weight-for-age and appetite as the most sensitive indicators for short-term nutrition programs, while linear growth requires longer intervention periods.