We examine consensual and coercive police–citizen relations in S~ao Paulo, Brazil. According to procedural justice theory, popular legitimacy operates as part of a virtuous circle, whereby normatively appropriate police behavior encourages people to self-regulate, which then reduces the need for coercive forms of social control. But can consensual and coercive police–citizen relations be so easily disentangled in a city in which many people fear crime, where the ability to use force can often be palpable in even mundane police–citizen interactions, where some people fear police but also tolerate extreme police violence, and where the image of the military police as “just another (violent) gang” has significant cultural currency? Legitimacy has two components—assent (ascribed right to power) and consent (conferred right to govern)—and consistent with prior work from the US, UK, and Australia, we find that procedural justice is key to the legitimation of the police. Yet, the empirical link between legitimacy and legal compliance is complicated by ambivalent authority relations, rooted in part in heightened cultural expectations about police use of force to exercise power. We finish the paper with a discussion of the theoretical and policy implications of these findings.