This article explores the genesis of Indonesian political Islam and its interactions with the nationalist secular state in the immediate post-colonial era while examining some of the origins of the ‘radical’ stream that has garnered much attention in the current post-authoritarian period. It puts forward the idea that, rather than an outcome of Indonesian democratisation, this stream was in fact the product of authoritarian New Order rule. The article also considers some parallels in the trajectories of political Islam more generally in Indonesia, the Middle East and North Africa, especially as a kind of populist response to the tensions and contradictions of global capitalism. It addresses the city of Surakarta (Solo) as a case study and highlights the importance of Cold War politics in moulding political Islam in Indonesia and elsewhere. The approach emphasises historical and sociological factors shaping political Islam that have tended to be relegated to the background in prevalent security-oriented analyses concerned with issues of terrorism and violence.