This study explores whether procedurally just interactions between police and citizens enhance perceptions of police legitimacy in high-crime environments. We conducted a representative in-person survey across five major Colombian cities, covering about 7 million residents. The survey included a vignette experiment presenting respondents with one of four scenarios that varied police officer respectfulness—characterized by clear communication of intentions—and neutrality. Our findings reveal that respectful behavior from officers significantly boosts citizens' perceptions of police legitimacy. In contrast, neutrality alone, or even combined with respect, does not affect these perceptions. This suggests that respect is an important component of procedural justice in fostering police legitimacy, while the standalone importance of neutrality is questionable. Policymakers should note that emphasizing respectful interactions in police training can foster greater trust and cooperation within communities, aiding effective crime prevention and community policing efforts. Conversely, focusing solely on neutrality without ensuring respect may be insufficient, possibly due to citizens' biases toward specific stereotypes.