To date, much of the analytical scholarship on policing in Africa has centred on non-state actors. In doing so, it risks neglecting state actors and statehood, which must be understood on their own terms as well as through the eyes of the people they supposedly serve. This article seeks to develop our theoretical and empirical understanding in this respect by exploring the contexts in which citizens seek to engage state police in Nigeria and South Africa. In doing so it highlights three particularly important uses that police contact may serve, that are currently being overlooked. State police can permit, authorize or limit crime control performed by others through informal regulatory intervention. They can exercise a unique bureaucratic power by opening a case which is valued as a record of right and wrongs to be used in the negotiation of everyday life, not simply as a means to legal prosecution. And finally, taking action ‘off the books’, the police can exercise a coercive power that can be termed ‘police vigilantism’, which citizens may try to harness for their own ends. We therefore argue that we should recognize the continued high public demand for the services of state police forces even in contexts where they fall short of expectations, and more closely analyse the ways in which people utilize and help to reproduce the police forces they condemn.