Background: Sexual minorities including men who have sex with men (MSM), face higher rates of poor mental health compared to the general population. In Europe, 18.4% of MSM report moderate or severe anxiety/depression, with 7.7% experiencing severe symptoms. Methods and Objectives: We conducted a respondent-driven sampling bio-behavioral study involving 1,300 MSM in Serbia-400 from Belgrade and 300 each from Novi Sad, Nis, and Kragujevac. Aiming to assess anxiety and depression prevalence, we used the Patient Health Questionnaire, version 4 (PHQ-4). We used translation from the validated Serbian PHQ-9 for two question, and for the other two adapted Serbian pilot version of the Generalized Anxiety Disorder, version 7 (GAD-7) scale. Results: Participants had a mean age of 31.1 years (±8.7), with Niš respondents being significantly younger (28.8 ± 8.4) compared to Belgrade, Novi Sad, and Kragujevac (31.5 ± 8.0, 31.9 ± 8.5, 32.2 ± 9.5, respectively; p < 0.001). Overall, 19.2% of MSM reported moderate or severe anxiety/depression, with highest rate in Nis (32%) compared to Belgrade (15.5%), Novi Sad (12.3%), and Kragujevac (18.3%; p < 0.001). Severe symptoms were reported by 5.6% of MSM, with highest prevalence in Nis (10.0%) compared to Belgrade (4.0%), Novi Sad (3.0%), and Kragujevac (6.0%; p < 0.001). Anxiety was reported by 24.9% of MSM, significantly more in Nis (48.7%) than in Belgrade (16.3%), Novi Sad (15.3%), and Kragujevac (22.3%; p < 0.001). Depression was reported by 19.2% of MSM, significantly more in Nis (29.3%) compared to Belgrade (12.5%), Novi Sad (14.3%), and Kragujevac (23%; p < 0.001). Conclusions: Although the PHQ-4 is not a diagnostic tool and may overestimate the prevalence of anxiety and depression, it indicates significant mental health concerns among MSM, particularly in Nis. There is a clear need for targeted behavioral and structural interventions to improve mental well-being of MSM.