Understanding the historical and sociological factors behind political Islam has tended to be relegated to the background in most of today’s security-oriented analyses, which are primarily concerned with issues of terrorism and violence. This paper considers the similarities between political Islam’s relationship to secular, national regimes in Indonesia, the Middle East and North Africa, as well as its role as a populist response to the tensions and contradictions of today’s global capitalism. It looks at the genesis of Indonesian political Islam, and investigates how today’s ‘radical’ Islamic groups and their leaders are connected to earlier Muslim organisations involved in the struggles against colonial rule and Soeharto’s ‘New Order’. It puts forward the idea that this radical stream was in fact the product of authoritarian New Order rule. The paper focuses on the city of Surakarta (Solo) as a case study and highlights the importance of Cold War politics in using and shaping political Islam in Indonesia and elsewhere.