The objective of this study was to analyze the association between ultra-processed food (UPF) consumption and mental health symptoms in a nationally representative sample of the Brazilian adolescent student population. Cross-sectional analyses with data from the National School-Based Health Survey (PeNSE 2019) were performed. Self-reported information was obtained for the frequency of five mental health symptoms in the last month and the consumption of thirteen UPFs in the last 24 h. Generalized linear models adjusting for the main confounders were performed for each sex. Of the 94,767 adolescent students (52.4% girls) included, 8.1% of the boys and 27.2% of the girls reported “almost always” or “always” having at least four of the five mental health symptoms. In the fully adjusted models, compared to the boys who consumed ≤3 UPF, those consuming ≥6 UPF reported more frequent symptoms of poor mental health (ß-coefficient = 0.27 [0.03, 0.51]; p-for-trend = 0.005). A similar association was observed in girls (ß-coefficient = 0.31 [0.13, 0.50]; p-for-trend = 0.001). In conclusion, in this large sample of adolescent students from an entire country, the higher the consumption of UPF was, the higher the frequency of reported symptoms of poor mental health. These findings remained significant regardless of sociodemographic and lifestyle factors, self-perceived body image, and bullying victimization.