In this article we address several tensions and dilemmas that are impacting on Australian principals and other school leaders. The first section explores areas associated with improving teaching and learning and includes discussion of education trends, the construction of new learning environments and the implication of these for more collaborative teaching, and the type of leadership needed for contemporary schools. The second section explores developing people with a particular focus on issues associated with ensuring teacher quality, rewarding teachers and leadership preparation. The third and final section explores two major external pressures: the introduction of a national curriculum, and increasing accountability through initiatives such as the public reporting of school performance data. Successful leadership is contextually sensitive, and successful leaders are able to cope with multiple tensions and dilemmas. Navigating the complex and demanding contemporary educational environment calls for successful school leadership on a scale not seen before, which has implications for how Australian school leaders are prepared and developed.