Objectives: We examine whether procedurally just police--citizen interactions increase police legitimacy in high-crime environments. Methods: We conducted an in-person representative survey of residents across five Colombian cities that comprise about 7 million people, including a vignette experiment. We presented each respondent with one of four scenarios that result from combining two sources of variation: whether the police officer was respectful---communicating her intentions, and whether she was neutral. Results: Our results suggest that when officers are respectful, citizens perceive the police as more legitimate. Neutrality, on the other hand, does not change citizens' perceptions of legitimacy---neither alone nor in combination with respect. Conclusions: Our analysis reinforces prior positive findings from vignette experiments assessing procedural justice theory, albeit adding uncertainty to the value of some of its individual components. We do so by using a representative sample of citizens, in a high-crime environment while including the interactions between different components of procedural justice.