Trust is essential to success at both the school and district levels. While its presence provides no guarantee of organizational success, its absence reliably predicts failure. Trust in institutions including the government, the church, and the media has declined in recent years. This is certainly true of public schools as well. The purpose of this qualitative study was to better understand the lived experiences of exemplary superintendents in developing trust and credibility. Participants included 12 current or former school superintendents who had received statewide recognition from their peers for ethical and capable leadership. The findings suggest that board-superintendent relationships and superintendent-principal relationships can have a substantial effect on trust in the organization. The findings also point to the importance of networking, supporting employees, and valuing dissent. Furthermore, insights are provided regarding the restoration of trust once it has been broken.