Background: Childhood undernourishment is a major public health problem globally, and being responsible for higher mortalities in children and enormous health costs in sub-Saharan Africa. However, scarcity of data on the magnitude of malnutrition and its underlying causes, especially in the pastoral system, limits the effectiveness of potential interventions. This study addresses the nutritional status and factors associated with malnutrition among children in Borana pastoral system, southern Ethiopia. Methods: A community based cross-sectional study, using multistage cluster sampling, was conducted from August to October 2015. Dietary diversity score (DDS), milk and meal frequencies, anthropometric measurements, and socio-economic variables were recorded for 538 children aged 6–59 months. Multivariable generalized linear model (GLM) with log link function was applied to ascertain determinants of malnutrition. The strength of association was assessed based on prevalence ratio (PR). Results: Prevalence of underweight, stunting, and wasting were 28.3 % (95 % CI: 24.4–32.1), 41.1 % (95 % CI: 36.7–45.1), and 9.8 % (95 % CI: 7.3, 12.4), respectively. Children who consumed more diverse foods were at a lower risk of being underweight (PR = 0.72, 95 % CL: 0.59–0.88), stunted (PR = 0.80, 95 % CL: 0.68–0.93) and wasted (PR = 0.42, 95 % CL: 0.27–0.66). Intake of increased milk frequency was also associated with lower risk of underweight (PR = 0.86, 95 %CL: 0.76–0.97), stunting (PR = 0.83, 95 %CL: 0.75–0.91) and wasting (PR = 0.73, 95 %CL: 0.56–0.96). The risk of underweight (PR = 1.02, 95 %CL: 1.01–1.03), stunting (PR = 1.01, 95 %CL: 1.00–1.02) and wasting (PR = 1.01, 95 %CL: 1.00–1.04) had increased with age, and no difference was observed between boys and girls. Children who lived far away from health care facilities were 1.2 and 2.4 times more likely to be stunted and wasted, respectively than those residing near a health care facility. Ownership of toilet and living close to market were associated with reduced stunting, whereas illness was associated with increased risk of underweight. Conclusions: The high prevalence of stunting among pastoral children is a serious public health concern and calls for urgent action. Association of nutritional status of children with dietary intake, and health status, access to health services and toilet availability underlines the need for improved nutrition practices, health care facilities and sanitary conditions in the study area.