Police legitimacy is an important topic of criminological research, yet it has received only sporadic study in societies where there is widespread police corruption, where the position of the police is less secure, and where social order is more tenuous. Analysing data from a probability sample survey of adults in Lahore, Pakistan, we examine the empirical links between people’s experience of police corruption, their perceptions of the fairness and effectiveness of the police, and their beliefs about the legitimacy of the police. Our findings suggest that in a context in which minimal effectiveness and integrity is yet to be established, police legitimacy may rest not just on the procedural fairness of officers, but also on their demonstrated ability to control crime and avoid corruption.