This cross-sectional study included 20,084 students from urban schools (first to fourth-grade) in Pelotas, Rio Grande do Sul State, Brazil. Weight and height were measured, and nutritional status was classified according to the World Health Organization (height deficit) and International Obesity Task Force (overweight and obesity) criteria. The study also recorded the variables age, gender, type of school, and schooling (grade-for-age adequacy). Prevalence of height-for-age deficit was 3.5% (3.9% in boys and 3.1% in girls). Prevalence rates for overweight and obesity were 29.8% and 9.1%, respectively. Overweight and obesity were more frequent in private schools, while height-for-age deficit was more frequent in municipal or State schools. For both boys and girls, age was positively associated with underweight and inversely related to overweight and obesity. Inadequate schooling was associated with increased risk of height deficit and decreased risk of overweight and obesity. In conclusion, primary students' nutritional status depends not only on demographic and socioeconomic factors, but also on type of school.