Abstract: Children younger than five years are the most vulnerable to diseases and malnutrition. A cross-sectional study was undertaken in rural areas of Nzega district in Tanzania to assess the prevalence and factors of malnutrition among children aged 6-59 months. Simple random sampling technique was used to select a representative sample of households with target children. The study enrolled 460 mother-child pairs from five wards. Data were collected using a semi-structured questionnaire. Child nutritional status was assessed based on anthropometric measurements. The potential contributing factors to malnutrition were also assessed. These included: child feeding practices, sociodemographic characteristics, access to water, sanitation, history of illness episodes (diarrhoea and acute respiratory infection) and child immunization status. The survey data were analyzed using SPSS for windows version 17.0 whilst anthropometric data were analysed using the ENA for SMART (2011) software. Almost all children (98.5%) were breastfed. It was found that about one quarter (25.6%) were breastfed immediately after birth and one third (33.5%) received pre-lacteal feeds. Prevalence of stunting (height- for- age Z score <-2), wasting (weight- for-height Z score <-2) and underweight (weight-for-age Z score <-2) were 26.1, 6.5% and 11.7%, respectively. Chronic malnutrition (stunting) was significantly (p<0.05) associated with child’s sex and age, mother’s education, number of antenatal care visits (ANC) and family size. Others factors were episodes of diarrhea, acute respiratory infection and access to safe water. Overall, the nutritional status of the children is sub-optimal and therefore, attention is needed to address the situation.