This article reports the findings of a study that sought to identify Muslim teachers' constructions of "masculinity" and "femininity" of the school principal. The first purpose of the study was to trace Muslim teachers' perceptions of masculine and feminine features of school principals, and the second was to explore their constructions of the desired principal-teachers relationship. Based on a qualitative investigation, this study found that male and female teachers hold cultural gender conceptualisations of the school principalship, which in turn influence the way they see power relations, leadership style and career development. Interestingly their preference for the ideal principal is not based on gender but rather on leadership qualities. Both female and male teachers prefer "the strong principal" who maintains moral behaviour, discipline and control in schools, yet is sensitive and collaborative. Likewise, male and female constructed ideas and favoured leadership features, values and behaviours are influenced by teachers' education and proximity to modern values. The practical implications of the study are discussed. (Contains 1 table.)