Low trust in state actors constrains state capacity, hindering growth and development. This paper studies how state actors can build public trust by improving the quality of their interactions with citizens. We first propose a mechanism linking improved interactions to public trust, defined as the belief that the state actor implements welfare-enhancing policies. Improved interactions lower the expected burden of engaging with the state actor, promoting compliance. This motivates citizens to believe compliance is worthwhile, increasing trust in the state actor. We then empirically assess the relationship between the quality of interactions and public trust in the Colombian National Police. We experimentally evaluate an intervention that retrains officers across five major cities in procedural justice principles such as fairness and respect while intensifying police-citizen interactions. The intervention was purposefully designed to be low-cost in terms of financial and human resources. We find that the intervention improved public trust, willingness-to-pay for police services, and citizens perceptions of fair treatment, suggesting low-cost interventions can help build trust between police and communities. We also find a limited impact on officers trust in citizens and their beliefs about citizens public trust, implying that institutional culture change may require more profound efforts.