In order to effectively fight criminal organizations, governments require support from significant segments of society. If citizens have a positive assessment of the executive’s job, the likelihood that they will report crimes, and act as allies in the fight increases. This provides important leverage for incumbents, and allows them to continue their policies. Yet, winning the hearts and minds of citizens is not an easy endeavor. Crime and violence affect citizens’ most valuable assets: life and property. Thus, one would expect a close relationship between public security and presidential approval? To generate robust answers to this question, and its multiple implications, we use Mexico as a case study, and use data at both the aggregate and at the individual level. We find that approval levels are indeed affected by crime, but not by all crimes. Perhaps surprisingly, they are not affected by the most serious of crimes: homicide. At the individual level, we find that support for the mere act of fighting organized crime has a stronger effect on approval than actual performance on public security. We also find no effect of crime victimization on approval at the individual level.