While life expectancy of people living with HIV is increasing, their burden of non-communicable diseases, including mental health disorders, is growing as well. The aim of this study is to investigate the prevalence and identify the risk factors associated with mental health disorders among this population in Rwanda. This cross-sectional study enrolled people living with HIV from 12 HIV clinics across Rwanda using random sampling. Trained HIV nurses conducted the Mini International Neuropsychiatric Interview to estimate the prevalence of major depressive episode, post-traumatic stress disorder, and generalized anxiety disorder. Sociodemographic, psychosocial, and HIV-related data were also collected. Associated risk factors for being diagnosed with one of the mental health disorders were assessed using modified Poisson regression with robust error variance. Of 428 participants, 70 (16.4%) had at least one mental health disorder with major depressive episode being most prevalent (n = 60, 14.0%). Almost all participants were adherent to antiretroviral therapy (n = 424, 99.1%) and virally suppressed (n = 412, 96.9%). Of those diagnosed with a mental health disorder, only few were aware of (n = 4, 5.7%) or under treatment for this mental health disorder (n = 5, 7.2%). Mental health disorders were associated with experiences of HIV-related stigma and discrimination (aRR = 2.14, 95%CI 1.30–3.53, p = 0.003). The results demonstrate underdiagnosis and undertreatment of mental health disorders among Rwandan People Living with HIV. Using HIV nurses to diagnose mental health disorders could serve as a low-cost strategy for integrating mental health care with existing HIV services and could inspire the implementation in other low-resource settings.