Maternal and child undernutrition is a pervasive and detrimental condition in Papua New Guinea. Despite rapid economic growth during the past decade, the stunting rate for children under 5, one of the primary indicators for child undernutrition, was estimated at 46 percent in Papua New Guinea in 2010, stagnant from 44 percent in 2005. This paper analyzes the association between the demographic, socioeconomic, environmental, and health-related factors on nutritional status for children under age 5 years, using the 2009–10 Papua New Guinea Household Income and Expenditure Survey. Stunting and underweight rates sharply rise in the first 24 months. Even in the better-off quintiles, children suffer from suboptimal breastfeeding and complementary food in the first 24 months. In general, the regression results showed that household wealth and geographic location are crucial factors that contribute to children's malnutrition. More importantly, food quality, measured by protein intake, has significant predicting power on child malnutrition. Broadly increasing socioeconomic status and improving the quantity and quality of caloric intake are general steps to improving health outcomes in Papua New Guinea. In addition, three key areas were identified as critical to alleviating the persistent and detrimental stunting rate in the country: (1) exclusive breastfeeding and complementary food; (2) interventions by health workers; and (3) nutrition education.