Trust and accountability are often positioned as opposites, the argument being that accountability is based on distrust and correction of identified deficiencies. Yet, trust is also important in order for accountability to lead to improvement; only when teachers and principals are open about the quality of their teaching and their school can there be a meaningful discussion about change. How can we overcome this dilemma? This paper will address the inextricable interaction between trust and accountability, presenting examples from a study in South Africa of how external control in a setting of distrust can undermine agency and improvement, and how high levels of trust can promote more effective accountability relationships. Our study provides relevant insights into why some education systems are unable to generate, evaluate and scale innovations in learning when a lack of trust and capacity leads to strong opposition to external accountability, and when strong bureaucratic accountability creates further inefficiencies in pressurizing educators across the education system to report and monitor on various aspects of education where these efforts do not actually improve the quality of teaching in the classroom or provide information on good practices.