The Quality of madrasa education depends on many factors like the leadership of headmaster which is crucial and influential to other supporting factors in maintaining and securing quality education of madrasa. This paper was aimed at investigating the leadership of madrasa headmasters in improving the quality of madrasa education in Maluku Province. It also investigated the contribution of headmaster leadership toward the teachers’ characteristic that contribute immensely to educational service. This study applied descriptive qualitative using a naturalistic approach. To achieve the objectives of the study, observations, interviews, and documentation were used in data collection techniques. The data collected were analyzed using Miles and Huberman model. The study found that the leadership of headmaster has contributed to the improvement quality of madrasa education. The leaderships included many aspects like the ability to create, plan, organize and communicate within organization of madrasa. The headmaster leadership also played significant role in building the characteristics of teacher like theological trait, physical, intelligence and personal charcteristics. Those characteristics are pivotal in improving teachers’ quality of educational service.