Trust is widely accepted as being central to domestic police effectiveness and legitimacy. It facilitates dealings between the public and the police, and eases relationships between the individuals within police services. In this article, we argue that trust has an equally fundamental role in international policing missions, yet establishing trustworthy policing arrangements is even more difficult, for a variety of reasons. We examine a number of these reasons here. The data used is drawn from interviews with Australian police on international deployment in Timor-Leste, the Solomon Islands and Papua New Guinea. As the data from case studies indicate, international policing missions often take place in countries with low levels of public trust in the police. For many in these countries, international interventions can be matters of ambivalence or even induce active resistance and resentment. Finding ways of cooperating and collaborating, if not trusting, are fundamental to achieving international policing mission objectives. The article therefore considers some ways in which these missions may minimize distrust and earn trust.