Oral health remains a global health problem. Mental health has been related to oral health behavior. However, studies among adolescents in high-income countries are limited. This study aimed to investigate the association of adolescents' mental health and well-being with regular toothbrushing. We used data from the 2018 Luxembourg Health Behavior in School-Aged Children study ( n = 7,561; n = 3,896 [51.5%] girls; mean [standard deviation] age = 14.9 [2.1] years). Multiple logistic regression analyses were performed to assess the associations of self-reported stress levels, life-satisfaction, somatic health complaints, and psychological health complaints with regular toothbrushing (≥2 daily). Analyses were adjusted for gender, age, family affluence, family structure, migration background, daily sugar consumption, smoking behavior, and general health. 70.5% of the adolescents regularly brushed their teeth. Adolescents who reported higher levels of stress (odds ratio [OR], 95% confidence interval [CI]; 0.97 [0.95;0.99] per one-point increase), low life-satisfaction (OR = 0.92 [0.89;0.95] per one-point increase), and psychological health complaints (OR = 0.95 [0.91;0.99] per complaint) were less likely to regularly brush their teeth. No association was found between somatic health complaints and regular toothbrushing (OR = 1.00 [0.94;1.06] per complaint). Adolescents with poor mental health and well-being are less likely to regularly brush their teeth and may have an increased risk for oral diseases. Interventions focused on lifestyle modification in adolescents with mental health problems should include regular toothbrushing to prevent dental caries and other oral diseases.