The paper reports on a study undertaken in Nairobi, Kenya with school leaders. We examined their perceptions of the adequacy of their preparation experiences and what aspects remained problematic. This paper only reports on the survey findings which included rating-type and open-ended responses. Principals conceptualized their apprenticeship/experiential preparation as useful for instructional leadership but reported the desire for formal qualification which would provide them with more credibility for their complex roles. Principals were primarily focused on survival and compliance with ministry expectations related to the managerial aspects of their role. Recommendations include a policy framework for leadership qualifications, competencies, and experience to provide standards and benchmarks designed to increase leader and system credibility.