Previous studies show detrimental effects of the COVID-19 pandemic and associated lockdowns on the lives of adolescents. Adolescents have experienced disruption in their daily routines, including changes in health behaviors such as an increased sedentary behavior and increased smartphone usage. The aim of this study was to assess the association of health behaviors with mental health problems in Austrian adolescents during the pandemic. Five cross-sectional surveys (February 2021 to May 2022) were performed during the pandemic assessing physical activity, smartphone usage, depressive symptoms (PHQ-9), anxiety symptoms (GAD-7), sleep quality (ISI-7), and stress (PSS-10). In total, N = 7201 adolescents (age: 14–20 years ((MW±SD): 16.63 ± 1.49 years); 70.2% female, 18.8% migration background) participated. A strong increase in mobile phone usage as well as a decrease in physical activity as compared to pre-pandemic data were observed (p < 0.001). Compared to the lowest smartphone user group (<1 h/d), the adjusted odds ratios (aOR) for all investigated mental health symptoms increased with increasing smartphone usage up to 3.2–6.8 in high-utilizers (>8 h/d). The aORs for depressive, anxiety, insomnia, and stress symptoms decreased in physically active compared to inactive adolescents. Results highlight the need for measures to promote responsible smartphone usage as well as to increase physical activity, so as to promote mental health in adolescence.