Background: Discretionary foods are not necessary for a healthy diet and are too high in saturated fat and/or added sugars, added salt, or alcohol and are low in fiber. The aim of this study was to identify patterns of discretionary food (DF) consumption in Polish adolescents in relation to anthropometric, socio-demographic, and lifestyle factors. It is important to learn about discretionary food consumption habits to identify health risks and plan strategies to reduce DF consumption. Methods: The cross-sectional study was conducted among 2849 primary school students aged 10–12 from Poland. Socio-demographic data, eating habits, lifestyle factors, and nutritional knowledge of children were assessed using questionnaires: KomPAN® and SF-FFQ4PolishChildren®. Body composition testing was performed by bioelectrical impedance analysis (BIA) using a TANITA MC-780 S MA multi-frequency segmented analyzer. Results: Four dietary patterns were identified with different frequencies of discretionary food consumption: LowDF, MediumDF, HighDF, and HighSweet pattern. Children from the LowDF and MediumDF patterns had higher BMI and body fat content than children from the HighDF and HighSweets patterns (p < 0.0001). The majority of children (68.4%) were of normal weight, 22.3% were overweight or obese, and 9.4% were underweight. Children in the LowDF and MediumDF patterns had higher body fat (24% and 23.5%, respectively) than children in the HighDF and HighSweetDF patterns (22.4% and 22.4%, respectively). Most of the children showed adherence to the MediumDF pattern, and they were mainly boys (38 vs. 32.5%). Girls predominate in LowDF, HighDF, and HighSweets patterns (33.5, 18.4, and 15.5%, respectively). Children in the LowDF and MediumDF patterns tended to be more physically active in their leisure time (OR = 1.758 (CI:1.32 2.34) p < 0.0001; OR = 1.354 (CI:1.04; 1.76) p = 0.0227) and the opposite relationship was observed in the HighDF pattern (OR = 0.495 (CI:0.38; 0.65) p < 0.0001). Children in the HighSweets pattern had low adherence to high physical activity (OR = 0.666 (CI:0.48; 0.92) p = 0.0132), but high adherence to moderate (OR = 1.29 (CI:1.01; 1.65) p = 0.0443) and high (OR = 1.54 (CI:1.04; 2.38) p = 0.0428) nutrition knowledge. Conclusions: Consumption of discretionary foods by Polish adolescents is related to body composition, socio-demographic, and lifestyle factors. Given the global emphasis on improving the daily diet, it seems necessary to implement intervention programs in Poland that would, among other things, clarify recommendations for the consumption of discretionary foods, following the example of other countries that have already achieved results in this regard. From a public health perspective, interventions to increase nutritional knowledge and improve lifestyles should be implemented with both adolescents and their parents in coordination with the school.