Aims This study aimed to examine the association between mental health problems and health-related quality of life (HrQoL) among in-school adolescents 13–19 years in the Harari region, eastern Ethiopia. Materials and methods A cross-sectional study was conducted on 3227 in-school adolescents aged 13 to 19 using multistage sampling. The KIDSCREEN-10 questionnaire assessed health-related quality of life (HrQoL), while a self-administered version of the strength and difficulty questionnaire (SDQ) examined mental health issues. Data were double entered, validated, and cleaned using EpiData version 3.1 and analyzed using STATA 14.1. An ordinal logistic regression model investigated the link between the outcome variable and the predictors. The results were reported using an odds ratio with a 95% confidence interval (CI), and a p-value of less than 0.05 was considered statistically significant. Results A quarter of the adolescents (23%) reported poor health-related quality of life; adolescents with internalizing and externalizing mental health problems had the lowest health-related quality of life. After controlling for potential confounders, adolescents with abnormal (AOR = 0.48, 95% CI: 0.39, 0.59) and borderline (AOR = 0.59, 95% CI: 0.45, 0.78) levels of internalizing problems had a 52% and 41% lower probability of having high HrQoL than those with normal levels. Furthermore, individuals with abnormal (AOR = 0.59, 95% CI: 0.45, 0.77) and borderline (AOR = 0.64, 95% CI: 0.45, 0.92) levels of externalizing difficulties had a 41% and 36% lower chance of having a high health-related quality of life. Conclusions Nearly a quarter of in-school adolescents had poor health-related quality of life. High scores for internalizing and externalizing mental health problems significantly impacted the adolescents’ health-related quality of life. This emphasizes the need to address mental health issues in the school setting to improve adolescents’ overall quality of life.