The article describes the transformation process of political Islam in Indonesia. Focusing on the early development period of the New Order regime, the paper seeks to examine how the period of intense conflict between Islamic political movements and the State was successfully resolved in the political arena. The conflicts developed at the beginning of independence. In 1966 the emergence of the New Order regime prevailed because of the military. The New Order marked the beginning of extensive efforts to stabilize the Indonesian political order and to find solutions for the problems of religious politics. Leaders and figures of the Islamic movements responded vehemently to the process as they sought to resolve the conflicts between Islam and the State. The modernization of Islamic thought in the 1970s marked an important moment for the search of alternatives. The modernization movement inspired a wide variety of accommodative policies within the New Order for religious agendas that were incorporated into the State political structure. The result is that the elements of an “Islamic state” could be implemented within the State institutions, without changing the national constitution of the Republic of Indonesia.DOI: 10.15408/sdi.v22i1.1389