While internationally there is a large body of quantitative work examining public perceptions of police, there is less in the way of qualitative, particularly anthropological, studies (Garriott, 2013). Moreover, as most studies are based in Western democratic nations with a strong rule of law, it is not surprising that findings have shown overall positive public perceptions of police. The case of Indonesia is different. The little quantitative work undertaken on public perceptions of police indicate extremely low levels of public trust and confidence (Muradi, 2014). This present study is thus unique in offering a qualitative analysis of a jurisdiction where public opinion is not favourably disposed towards the police. Drawing on ethnographic data collected between 2008 and 2013, this article critically explores what Indonesians think of their police service, and what they want from their police service in the future. The findings indicate that while people loath police corruption, eradicating corruption is not cited as a top priority. Furthermore, while people express a desire to have a police force that can deter, investigate, and solve crime, these factors do not dominate thinking. Rather, people form judgements of police based primarily on how they, or people they know, are treated by police, sentiments encapsulated in notions of procedural justice policing (Tyler, 1990). It is well-established that public support is essential to effective policing (Murphy & Cherney, 2012), and as such taking into account public desire for a respectful police force above a focus on outcome based policing will significantly aid police reform projects in Indonesia.