Trust is recognized as a critical component of effective leadership. One way trust forms is through the experiences in the history of communication transactions between individuals. This study was a first step to test the relationship between communication competence skills and trust in leaders. A sample of 1,138 international school teachers in the East Asian Regional Council of Schools responded to a survey which measured teacher perceptions of the communication competence and trustworthiness of their principal. The findings showed a significant relationship between the three communication competence factors and trust, and that the attentiveness-coordination factor was the strongest predictor of trust.