This paper discusses the relation between Islam and the State as experienced by Indonesian Muslims. Using the historical analysis it begins to delineate the struggle for political Islam in Indonesia with their diverse aspirations from the very beginning of Indonesia as a nation state until the collapse of Suharto regime. In terms of Islamic political struggle, this explains that there was a shift from legalistic-formalistic Islamic political articulation in the Old Order and the beginning of New Order Era into more substantiality pragmatic method. This eventually leads to the formation on the theorization of political Islam since there is no a single definitive theory of political Islam in the Islamic scholarship. Muslims in Indonesia have offered a brilliant concept Pancasila' as a solution in the multicultural situation like Indonesia. Pancasila was considered not only by the founding fathers of Indonesia but also by majority of Indonesian Muslims as an interpretation and contextualization of Islamic Politics in the pluralist society of Indonesia in order to create more harmonious and peaceful life. Key Words: Islam, State, Muslim Politics