This article tries to contextualise the formulation of Islamic laws with regards to contemporary dynamics of non-Muslim leadership in the government. It particularly addresses the religious deliberation (ijtihad) of the traditionalist Muslim organisation, the Nadhlatul Ulama/NU, and its youth organisation, the Gerakan Pemuda Ansor. The construction of Islamic laws in contemporary Indonesia tells an insightful viewpoint in Islamic-laws making and delivers multiplicity in Islamic interpretation. Despite the fact that these two organisations are of the same organisation, the NU, their formulation of Islamic laws with regards to non-Muslim leadership demonstrates a different and contrasting opinion. While the national board of the NU through its national congress in 1999 argues against non-Muslim leadership, the national religious deliberation board (bahtsul masail) of the Ansor in 2017 issues a legal opinion that approves non-Muslim leadership. As this article argues, the different opinions between these two institutions develops particularly because of different construct in defining Islam and democracy in the largest Muslim country Indonesia. They differ in reconciling istinbat (methods for formulating the laws) of two principles of Islamic laws (ushul al-fiqh); al-sabit (permanent) and al-mutahawwil (change). It further argues that the national board of the NU particularly sees the prohibition of non-Muslim leadership as al-sabit, an unchanged dictum, whereas the Ansor considers it al-mutahawwil as looking at the Indonesian state constitution that does not discriminate its citizens based on religion. Thus, making Islamic laws accords to the state constitution.