As many countries note declining trust in government institutions, the academic and public focus is largely on the relationship with government performance. While some existing work points to this being a tenuous connection, there has been minimal attention paid to other methods of persuasion. In this project, I explore one of the ways governments and leaders seek to shift public perceptions: storytelling. I use the case of the main investigative service in Kenya, the Directorate of Criminal Investigations, which has been sharing true stories of their cases on Twitter as a way to build trust in the police. Using sentiment classification, I show that following these stories causes people to write more positively about the police. I also build on burgeoning methods for story modeling and generation to test whether adhering to a classic story structure makes these narratives more persuasive. This project aims to contribute to our understanding of how trust develops and whether structure of communication as well as content matters.