Surrounded by an environment of constantly changing social, technological, and natural conditions, today’s schools must dynamically improve and adapt to these conditions in order to survive. In this context, school leaders play an important role as the main drivers of innovation and change in education, trusting their team of teachers, and encouraging teachers’ innovativeness. Against this background, our study highlights the importance of creating an innovative working climate characterised by trust and experimentation. Our study is based on a cross-sectional, randomised and representative data set of N = 411 school leaders in Germany and applies mediated structural equation modelling. It examines the effect of school leader trust in teachers on teachers’ collective innovativeness as a prerequisite for school improvement and change, and the mediating role of individual and organisational exploration and exploitation as components of ambidexterity. The results of our analysis point to three main findings: First, school leaders’ trust in teachers has a significant direct relationship with teachers’ collective innovativeness. Second, the mediating variables of both school leader and school exploration have significant relationships with collective teacher innovativeness. Third, school leader exploration and exploitation are micro-foundations of organisational ambidexterity. By identifying manageable levers of change and providing prescriptive guidance on how schools can respond to dynamically changing environments, our study has implications for a theory of school improvement and change, for the practice of school improvement and change, and for education policy and frameworks for the training and professional development of teachers in general and school leaders in particular.