The downfall of the New Order Regime in 1998 brought about significant change to Indonesia’s public sector.  Law number 22 of 1999, further refined by Law 32 of 2004, provide legal bases for district governments to administer the public sector. The central government also introduces the notion of good governance through the promulgation of various regulations. For Madrasah however, decentralization policy failed to provide clear legal bases as to how it relates to district government. Law 32 of 2004 verse 10 article 3 retains the centralized management by the Ministry of Religious Affairs. This however does not exclude Madrasah from public demand of implementing the principle of good governance. This study analyses the dynamics of principal-ship both in the Sekolah and the Madrasah in the era of decentralization. By comparing two research sites, this study sought to create better understanding about the context by which the organization climate of two different schools are shaped, and how principals and teachers perceives the notion of school leadership in the light of most recent policy development. To do this, interviews were undertaken and questionnaire-based data collection was also conducted. The study found that in the ground level implementation of decentralization policy, Sekolah developed more rigorous leadership compared to that in the Madrasah. This research recommends the adoption of stronger regulation regarding principal-ship of Madrasahs in order to create an environment that is more in tune with the spirit of public service reforms.