A principal plays a very important role in deciding the direction and success of a school. Whether a school is dynamic is dependent upon the skills and abilities of the principal. In order to be excellent, the principal must be in possession of an excellent character. Therefore, the selection and promotion of school principals should be conducted through a meticulous and objective procedure. The entire process must be reviewed in order to ensure the quality and high standard of national education. Selection according to seniority or competency in work performance through evaluation of management and administrative skills, which is the current practice, may not be suitable for the enhancement of the leadership of principals. This study was conducted to identify and affirm the conceptual framework and attributes of school leaders (principals) needed to achieve leadership sustainability and school excellence. The exploratory factor analysis method was employed for the purpose of this study and was implemented in three stages. The sample population comprised primary and secondary school teachers. Through this study, it was found that there were five important traits or attributes which a school leader or principal must possess in order to make a school excellent. These five attributes are: (i) integrity, which has the sub-attributes of being principled and humble; (ii) forward looking, which has the sub-attributes of strategic catalyst and mind motivator; (iii) inspirational, which has the sub-attributes of supportive and influential; (iv) competent, which has the sub-attributes of task competency (there are two components, namely, action-oriented and sociability as well as emotional and spiritual competency); and (vi) self-efficacy.