Residents of some neighborhoods often experience an overwhelming police presence that intrudes upon their lives, and yet feel unprotected by law enforcement agents who neglect safety provision, in a process named by the literature the overpolicing-underpolicing paradox. In the context of one of the most unequal cities in the world, this study provides a quantitative assessment of the dynamics and the consequences of this apparent paradox. Drawing upon a three-wave longitudinal survey representative of adult residents of eight neighborhoods in São Paulo, Brazil (N = 1,200), I demonstrate that perceptions of police intrusion and cynicism about police protection (a) dynamically reproduce each other over time, (b) share similar correlates, most notably related to exposure to structural disadvantage and aggressive policing practices, and (c) undermine beliefs about the legitimacy of the police. This study provides further evidence that the demand for public safety in disadvantaged communities does not seem to be solved by policing strategies centered around the increase of intrusive practices and highlights the relevance of exploring public-authority relations in understudied Global South settings. I conclude with a discussion about how the unbalanced distribution of repression and protection by legal institutions can send relational messages of exclusion, marginalization, and neglect to members of the public.