Gus Dur and KH Afifuddin Muhajir are two intellectual figures of Nahdlatul Ulama who have deep mastery in the fields of Fiqh and Usul Fiqh. His deep mastery of these two scientific fields led them to become moderate, contextualist, and substantive fiqh experts. They both have contributed ideas that are important in the concept of the Islamic state system. Their thoughts are able to provide textual and contextual answers to groups that require the establishment of an Islamic state. Uniquely, the answers presented are based on Islamic texts contained in fiqh books. There are two important issues discussed in this article. First, the principles of the Qur'an and Hadith regarding the Islamic state system. Second, the religious moderation thought of Gus Dur and KH Afifuddin Muhajir about the Islamic state administration system. After going through the discussion, it was concluded that among the principles of the state administration system from the perspective of the Al-Quran and Hadith are justice, equality, collective deliberation, freedom, and supervision of the people. The establishment of an Islamic state is included in the realm of ijtihadiyyah because there are no standard rules in the Qur'an and Hadith related to certain forms and systems of government. The religious moderation thoughts of Gus Dur and KH Afifuddin Muhajir about the Islamic state administration system include that religion must be the moral and ethical foundation in the state, while the state must be a protector for the whole community. For both of them, the most important thing is to fight for Islamic values ​​and realize the maqosid sharia of establishing a state, not institutional Islamic formalism.