This article analyses a dramatic political transformation in Indonesia's Aceh province. In the 1950s, an Islamic rebellion (Darul Islam) aimed not to separate Aceh from Indonesia, but rather to make Indonesia an Islamic state. A successor movement from the 1970s was GAM, the Free Aceh Movement. GAM, however, was essentially secular-nationalist in orientation, sought Aceh's complete independence and did not espouse formal Islamic goals. The transformation is explained by various factors, but the key argument concerns the relationship between Islam and nationalism. The defeat of Darul Islam had caused Aceh's Islamic leaders to focus on what they could achieve in Aceh alone, ultimately giving rise to Acehnese nationalism and the secessionist goal. However, Islam remained a point of commonality with, rather than difference from, majority-Muslim Indonesia. The logic of nationalist identity construction and differentiation thus caused Aceh's separatist leaders, despite being personally devout, to increasingly downplay Islamic symbols and ideology.