The empirical research for this paper was undertaken with leaders of early years setting in the Kingdom of Saudi Arabia (KSA). The investigation sought to establish to what extent it was possible to behave in line with the concept of pedagogical leadership in the twenty-first century in an Arab Muslim monarchy, dominated by Islam, where directive leadership and control by the state has been the traditional norm. Education in KSA is now subject to reform, however, with leadership roles and responsibilities becoming a key issue and the early years sector being one of the major targets for development.