Depression is a major public health problem in the Russian Federation and is particularly of concern for men who have sex with men (MSM). MSM living in Moscow City were recruited via respondent-driven sampling and participated in a cross-sectional survey from October 2010 to April 2013. Multiple logistic regression models compared the relationship between sexual identity, recent stigma, and probable depression, defined as a score of ≥23 on the Center for Epidemiological Studies Depression scale. We investigated the interactive effect of stigma and participation in the study after the passage of multiple "anti-gay propaganda laws" in Russian provinces, municipalities, and in neighboring Ukraine on depression among MSM. Among 1367 MSM, 36.7% (n = 505) qualified as probably depressed. Fifty-five percent identified as homosexual (n = 741) and 42.9% identified as bisexual (n = 578). Bisexual identity had a protective association against probable depression (reference: homosexual identity AOR 0.71; 95%CI 0.52-0.97; p < 0.01). Those who experienced recent stigma (last 12 months) were more likely to report probable depression (reference: no stigma; AOR 1.75; 95%CI 1.20-2.56; p < 0.01). The interaction between stigma and the propaganda laws was significant. Among participants with stigma, probable depression increased 1.67-fold after the passage of the anti-gay laws AOR 1.67; 95%CI 1.04-2.68; p < 0.01). Depressive symptoms are common among MSM in Russia and exacerbated by stigma and laws that deny homosexual identities. Repeal of Russia's federal anti-gay propaganda law is urgent but other social interventions may address depression and stigma in the current context.