This paper’s focus is Russia, a country where trust in police has been low for decades. We examine key factors that explain citizens’ assessments of risk and safety, perceptions of police legitimacy and engagement in precautionary behaviors. We further explore the relationship between gender, prior victimization, and neighborhood incivilities to explain citizens’ safety perceptions. Two key findings emerge from a survey of millennials from St. Petersburg, Russia. Police legitimacy is a strong predictor that is positively related to citizens’ safety perceptions. However, engagement in precautionary behaviors is inversely related to respondents’ safety and risk perceptions. In addition, we have found that being a female is a strong predictor of feeling unsafe, a finding consistent with studies from other parts of the world. Neighborhood incivilities are negatively associated with safety perceptions, but its effect was only marginal for men in the subgroup analysis. Implications for the citizens’ practices of engagement in co-producing safety versus enhancing police legitimacy and the police role in enhancing risk and safety perceptions are discussed.