Background: Undernutrition among children has become a major public health issue due to the high risk of morbidity and mortality involving this vulnerable age group. This study focused on the rural population, especially among the Dayak children in Sarawak, Malaysia. Methodology: This community-based cross-sectional study was conducted in Sarawak’s rural areas using a multistage stratified cluster sampling technique. Data were collected through face-to-face interviews using an interviewer-guided questionnaire. The nutritional status of the under-five children was measured according to the World Health Organization guidelines. The nutritional indicators were calculated as z-scores. Multivariate logistic regression analyses were performed using SPSS to identify the factors associated with nutritional status. Results: The prevalence of undernutrition among the under-five Dayak children in the rural areas of Sarawak was 39.6%. The analysis suggested that wasting was predominantly associated with parental education levels of primary and below, poor wealth index, environmental and sanitation issues, children with history of low birth weight, shorter duration of exclusive breastfeeding, and poor appetite. Stunting was high within the age group of <3 years old and was associated with parents’ occupation and household wealth index. Low parental education, poor wealth index, environmental and sanitation issues, poor appetite, and the children’s recent illness predicted underweight. Conclusion: These findings imply that a multi-sectoral and multi-dimensional approach is essential to address undernutrition in rural settings. Improvement on households’ socioeconomy, environment and sanitation should be emphasised to reduce undernutrition among the children.