The study reported here aimed to develop an understanding of leadership at the primary school level, particularly regarding madrasah primary schooling, in a context of challenging circumstances geographically and demographically in Indonesia. It investigated three interrelated aspects of madrasah primary school leadership, namely, the historical background to madrasah school leadership, the recent developments in relation to madrasah school leadership, and issues of concern for madrasah primary school leaders. The study was guided by the theoretical underpinning of interpretivism. Accordingly, qualitative methods of data collection were employed including semi-structured interviews and document study. Grounded theory methods were employed to analyse the data. The results related to the historical background to primary school leadership from 1945 to 1998 revealed that throughout this period the Indonesian government gradually developed a highly centralised governance resulting in the tightly controlled management of madrasah primary schools that debilitated madrasah primary school leadership. More recently, however, the government has devoted greater attention than previously to madrasah education, although, because this sector falls under the aegis of the Ministry of Religious Affairs, it is not decentralised. This has led to more structural constraints than apply in the case of State schools. Amongst the principal current concerns faced by madrasah primary school leaders are those encountered in relation to 'teachers', 'infrastructure', and 'management'. Certain issues specifically in relation to 'students', 'finance' and 'staffing' also arise at some but not all madrasah. Overall, this narrative depicts rare insights into the highly distinctive context of Indonesian madrasahs.