Background: Globally, malnutrition accounts for at least half of all childhood deaths. Managing malnutrition in the community settings involves identifying malnutrition using a universally validated screening tool and implementing appropriate interventions according to the degree of malnutrition. The aim of this study was to estimate prevalence and associated factors that result in malnutrition among children under-five years of age in Thatta and Sujawal districts in Sindh province, Pakistan. Methods: A cross-sectional survey was conducted between May and August 2014. A total of 3964 children under-five years were enrolled in the study. The WHO growth standards height-for-age Z-scores (HAZ), weight-for-height Z-scores (WHZ) and weight-for-age Z-scores (WAZ) were used to measure stunting, wasting and underweight. A structured questionnaire was used to collect data on socioeconomic conditions, family size, maternal education, parity and child morbidity. Multivariable logistic regression was used to determine the risk factors for malnutrition. Results: The prevalence of stunting, wasting and underweight were 48.2% (95% CI: 47.1-50.3), 16.2% (95% CI: 15.5-17.9), and 39.5% (95% CI: 38.4-41.5), respectively. Stunting was slightly higher (51%) in boys than in girls (45%) (p < 0.001). The proportion of wasting (p = 0.039) and underweight (p = 0.206) was not significantly different between boys and girls. Fifty percent children in the poorest households were stunted as compared to 42% in the wealthiest households. Children in the poorest households were two times more likely to be wasted (20.6%) than children in the wealthiest households (10.3%) (OR 2.33, CI 1.69-3.21, p < 0.001). A similar relationship was observed between household wealth and underweight in children (43.8% in poorest and 28.8% in wealthiest households (OR 2.18, CI 1.72-2.77, p < 0.001). Household wealth was significantly associated with stunting, wasting and underweight. Diarrhea was associated with underweight. Factors such as mother's education, parity and family size were not associated with malnutrition in our study area. Conclusions: The findings of our study revealed that malnutrition was widespread among the children under-five years of age. The food/nutrient based interventions together with improved hygiene practices and household wealth should be targeted to improve malnutrition situation in the study area and in the country.