Background: Poor diet quality may contribute to undernutrition, particularly affecting young children from low-income households. Therefore, affordable and healthy local food-based recommendations (FBRs) are needed. Objectives: This study aimed to (1) identify problem nutrient(s), (2) identify locally available nutrient-dense food sources that can provide adequate nutrients to meet the recommended dietary intakes of undernourished urban poor children aged 2-5 years, and (3) use linear programming to recommend a daily diet based on the current food patterns that achieves dietary adequacy and meets average food costs for these children. Methods: A cross-sectional study was conducted in Seremban, Malaysia. Three-day 24-hour dietary recalls were collected from the mothers (n = 168). Food costs were estimated using market surveys. The FBRs were formulated by linear programming analysis using Optifood software. Results: Folate was an “absolute problem nutrient” (such a nutrient does not achieve the 100% recommended nutrient intake even upon diet optimization). Full-cream milk, chocolate malted milk, fortified cornflakes, and chicken egg were the common locally available nutrient-dense foods that would provide adequate nutrients to meet the recommended dietary intakes of undernourished urban poor children. The final FBR set would ensure dietary adequacy for 8 to 9 of 11 nutrients at a cost of ringgit Malaysia (RM) 4.80/day (US $1.05/day) and RM6.20/day (US $1.34/day), depending on the age group. Conclusions: Interventions are required to ensure dietary adequacy for undernourished urban poor children under 5 years old. Dietary adequacy could be improved via realistic changes in habitual food consumption practices. © The Author(s) 2025.