Objective To describe and compare the nutritional status of adolescents using three criteria for nutritional status classification (Conde & Monteiro, International Obesity Task Force - IOTF and Word Health Organization - WHO), to analyze the correlation between these three criteria as for the overweight proportion, and to investigate whether factors associated with overweight and obesity differ among the three criteria. Methods Demographic (gender, age, geographic area) and anthropometric (body weight, height) variables were measured in 33.728 adolescents aged 11 to 17 years. The following criteria were investigated: IOTF (2000); Conde & Monteiro (2006); and WHO (2007). Results The overall overweight prevalence was 20.6% for the Conde & Monteiro criteria; 15.3% for the IOTF criteria and 20.1% for the WHO criteria. Both for boys and girls, the estimated overweight prevalence using the Conde & Monteiro and WHO criteria were higher than that using the IOTF criteria. Higher concordance was found between the Conde & Monteiro (2006) and WHO (2007) criteria for all age groups. Regarding associated factors, similar associations were found for the three criteria for higher BMI classification: being male, 11–12 and 13–14 years of age and living in the Midwestern, Southeastern and Southern regions of Brazil. Conclusion The criteria for BMI classification estimate overweight prevalence in a different way, and the criteria proposed by Conde & Monteiro resulted in higher prevalence in both sexes. Higher concordance between the Conde & Monteiro and WHO criteria was found for all age groups. The groups most vulnerable to showing overweight and obesity for the three criteria for BMI classification were males, age 11–12 and 13–14 years, and living in the Midwestern, Southeastern and Southern regions of Brazil. Overweight and obesity are considered a public health problem prevalent among adolescents in Brazil, regardless of the criteria adopted.