Within the past 80 years, leadership has been a serious discussion and it is also considered important to understand what variables relevant to effective leadership. Among these variables, gender is so critical and as a result it must be examined with regard to optimizing leadership effectiveness in professional, political, cultural, and personal realities of the twenty-first century as well as in school. In this century, women and men have been, are, and should be leaders. However, there are some factors that effect their leadership practices. To this end, this research aims to determine the factors that affect teachers' trust in male and female school leaders. The study employed a qualitative research design. The data were collected with interview technique. In this regard, 20 teachers were interviewed. The participants were determined with purposeful sampling method. The data were analyzed with inductive analysis method. Results revealed that the participant teachers trust different behaviors or characteristics of their male or female leaders. In general, teachers trust in their female leaders' more because of their objective, idealistic, dedicated behaviors, and also their motherly, sensitive and compassionate personality. On the other hand, teachers trust in their male leaders as they are fair, trustworthy, frank, competence, more rational and strong communicators. While male leaders are believed to take initiative and implement the laws and regulations more strictly, female administrators are more interested in the administration profession, behave meticulously and work devotedly. It is recommended that school administrators should create a climate of objectivity and trust in school.