Beginning principals are faced with many challenges when entering a new building; including learning the culture and identifying the needs of staff and students. It is the role of the principal to lead the school in change meant to improve outcomes for students. Establishing trusting relationships with teachers increases the likelihood that change will take hold. The purpose of this study was to highlight the experiences of three Catholic school principals who were successful in establishing trust to inform all beginning principals as they attempt to do the same. Findings indicate that Tschannen-Moran's (2004)five facets of trust: benevolence, reliability, openness, competence, and honesty were present for each principal. In addition, follow-through, shared and transparent decision-making and frequent and meaningful teacher contact (Chhuon, Gilkey, Gonzalez, Daly, & Chrispeels, 2007)were critical to establishing trust. Presence as a leadership characteristic was identified as a subject for future study.