Background: Food insecurity significantly impacts children’s health, affecting their development across cognitive, physical, and socio-emotional dimensions. This study explores the impact of food insecurity among children aged 6 months to 5 years, focusing on nutrient intake and its relationship with various forms of malnutrition. Methods: Utilizing machine learning algorithms, this study analyzed data from 819 children in the West Bank to investigate sociodemographic and health factors associated with food insecurity and its effects on nutritional status. The average age of the children was 33 months, with 52% boys and 48% girls. Results: The analysis revealed that 18.1% of children faced food insecurity, with household education, family income, locality, district, and age emerging as significant determinants. Children from food-insecure environments exhibited lower average weight, height, and mid-upper arm circumference compared to their food-secure counterparts, indicating a direct correlation between food insecurity and reduced nutritional and growth metrics. Moreover, the machine learning models observed vitamin B1 as a key indicator of all forms of malnutrition, alongside vitamin K1, vitamin A, and zinc. Specific nutrients like choline in the “underweight” category and carbohydrates in the “wasting” category were identified as unique nutritional priorities. Conclusion: This study provides insights into the differential risks for growth issues among children, offering valuable information for targeted interventions and policymaking.