Pemberontakan di Aceh
memulai kegiatan separatis itu antara tahun 1974 dan 1976, ia mengandalkan jaringan kerabatnya dan sejumlah intelektual muda yang berpikiran sama untuk menyebarkan pesannya yang kemudian memperoleh massa simpatisan, khususnya di Medan, Sumatera Utara. Aspinall juga menuliskan ingatan para simpatisan GAM tentang hari-hari awal pemberontakan dimana mereka akan menyebarkan pamflet kepada teman atau menyelipkannya secara anonim di bawah pintu kantor rekan-rekan mereka.
Namun hasil dari upaya propaganda tersebut cukup berbeda-beda. Eric Morris ketika mewawancarai pendukung GAM tahun 1983 untuk tesisnya mencatat bahwa, daripada untuk kemerdekaan, para pendukung GAM lebih tertarik baik pada sebuah negara Islam Indonesia atau bagi Aceh untuk diperlakukan lebih adil oleh pemerintah pusat. Aspinall juga mencatat bahwa untuk beberapa daerah, GAM tidak membedakan
dirinya dari Darul Islam atau Partai Persatuan Pembangunan yang berkampanye di atas panggung Islam untuk Pemilu legislatif Indonesia tahun 1977. Namun bagi individu yang telah menjadi pendukung inti GAM, pesan kemerdekaan yang ditemukan dalam propaganda GAM dipandang sebagai pewahyuan Islam dan banyak yang merasakan momen kebangkitan Islam.
Banyak anggota GAM adalah entah anggota pemberontakan Darul Islam atau anak-anak dari mereka. Aspinall mencatat bahwa hubungan kekerabatan, antara ayah dan anak serta antara saudara, telah menjadi penting dalam membentuk solidaritas GAM sebagai sebuah organisasi. Banyak yang merasa bahwa mereka sedang melanjutkan aspirasi ayah, paman, saudara atau sepupu laki-laki yang biasanya
adalah orang-orang yang melantik mereka menjadi anggota GAM; dan orang-orang yang aktivitas atau kematiannya di tangan aparat keamanan negara telah mengilhami mereka untuk bergabung dengan GAM. Konstituen GAM juga sering merupakan penduduk masyarakat pedesaan dimana semua orang tahu dan kenal erat dengan tetangga mereka. Adanya pertalian erat ini memungkinkan kesinambungan serta resistensi tingkat tinggi terhadap infiltrasi oleh aparat intelijen negara.
Aspinall juga mengakui kuatnya ketahanan GAM ada pada strukturnya yang seperti sel pada tingkat yang lebih rendah. Tingkat di bawah komandan militer regional (atau "panglima wilâyah") adalah satuan yang diperintah oleh komandan junior ("panglima muda") dan bahkan komandan tingkat yang lebih rendah ("Panglima Sagoe" dan "Ulee Sagoe") yang tidak mengetahui
identitas rekan-rekan mereka di daerah tetangga dan hanya mengenal mereka yang langsung berpangkat di atas mereka. Karakter ini memungkinkan GAM untuk bertahan sebagai sebuah organisasi meskipun ada di bawah upaya penekanan kuat oleh aparat keamanan negara Indonesia.
Robinson mengatakan bahwa penggunaan teror oleh militer Indonesia dalam aksi kontra-pemberontakan melawan GAM dalam periode rezim "Orde Baru" pertengahan 1990 (dalam tahap kedua pemberontakan) telah menyebabkan meluasnya dukungan dari masyarakat Aceh yang terpengaruh oleh kebijakan militer Indonesia tersebut, dan mendorong mereka untuk menjadi lebih simpatik dan mendukung GAM. Ia menilai
bahwa metode militer tersebut malah memiliki efek meningkatkan tingkat kekerasan, mengganggu masyarakat Aceh, dan luka yang ditimbulkan terbukti sulit untuk disembuhkan. "Amnesty International" mencatat:
"Amnesty International" mendokumentasikan penggunaan penangkapan sewenang-wenang, penahanan di luar legalitas, eksekusi, perkosaan dan pembumi-hangusan sebagai karakter operasi militer Indonesia terhadap GAM sejak tahun 1990. Di antara tindakan yang lebih mengerikan diamati oleh "Amnesty International" adalah pembuangan publik mayat-mayat korban eksekusi (atau "Penembakan Misterius") yang dilakukan
sebagai peringatan untuk orang Aceh untuk menahan diri dari bergabung atau mendukung GAM. Berikut ini adalah deskripsi tindakan tersebut oleh "Amnesty International":
Taktik TNI lain yang dipertanyakan adalah aktivitas yang disebut "operasi sipil-militer" dimana warga sipil dipaksa untuk berpartisipasi dalam intelijen dan operasi keamanan. Sebuah contoh terkenal dari hal ini adalah "Operasi Pagar Betis" seperti yang dijelaskan oleh "Amnesty International" berikut:
Damien Kingsbury, yang menjabat sebagai penasihat informal pimpinan GAM di Swedia selama Perundingan Damai Helsinki 2005, menyatakan bahwa militer Indonesia memiliki kepentingan tersembunyi di Aceh sehingga mereka sengaja menjaga konflik supaya tetap terjadi di tingkat yang akan membenarkan kehadiran mereka di provinsi bergolak tersebut. ICG juga menegaskan dalam sebuah laporan tahun 2003 bahwa, "Aceh
(adalah) tempat yang terlalu menguntungkan untuk para perwira militer yang sangat bergantung pada pendapatan yang bersumber non-anggaran."
Dinyatakannya status darurat militer di Aceh oleh pemerintah Indonesia pada Mei 2003 menghasilkan perlawanan terpadu oleh militer Indonesia terhadap GAM. ICG melaporkan bahwa pada pertengahan 2004, jalur pasokan dan komunikasi GAM terganggu secara serius. GAM juga makin sulit berpindah-pindah dan keberadaan mereka di kawasan perkotaan hilang sepenuhnya. Akibatnya, komando GAM di Pidie menginstruksikan kepada
semua komandan lapangan melalui telepon agar mundur dari "sagoe" (subdistrik) ke "daerah" (distrik) dan aksi militer hanya dapat dilaksanakan jika ada perintah dari komandan daerah disertai izin komandan wilayah. Sebelumnya, saat GAM masih kuat, satuan tingkat "sagoe"-nya memiliki otonomi komando yang lebih besar sehingga mampu melancarkan aksi militer atas kemauannya sendiri.
Menurut Endriartono Sutarto yang saat itu menjabat Komandan Jenderal ABRI, pasukan keamanan Indonesia berhasil mengurangi jumlah pasukan GAM sebanyak 9593 orang- yang diduga mencakup anggota yang menyerahkan diri, ditangkap, dan tewas dalam baku tembak. Meski meragukan keakuratan jumlah tersebut, banyak pemantau sepakat bahwa tekanan militer yang baru terhadap GAM pasca penerapan darurat militer memberikan pukulan telak bagi GAM.
Akan tetapi, Aspinall mencatat bahwa sebagian besar petinggi GAM yang ia wawancarai, terutama petugas lapangan, bersikeras bahwa mereka mengakui MoU Helsinki bukan karena militer mereka semakin lemah. Mantan pemimpin GAM Irwandi Yusuf, yang kelak menjadi Gubernur Aceh melalui pilkada langsung tanggal 11 Desember 2006, mengaku bahwa bukannya bubar, situasi GAM justru membaik sejak anggota
yang sakit dan lemah ditangkap militer Indonesia sehingga anggota di lapangan tidak terbebani oleh mereka. Walaupun pasukan GAM tetap komit melanjutkan perjuangan mereka, para petinggi GAM mungkin sudah putus asa membayangkan mungkinkah mencapai kemenangan militer atas pasukan pemerintah Indonesia. Kata mantan perdana menteri GAM Malik Mahmud kepada Aspinall bulan Oktober 2005: "Strategi yang diterapkan oleh kedua pihak
berujung pada kebuntuan yang sangat merugikan". Saat diwawancarai "Jakarta Post" tentang apakah mengakui MoU Helsinki adalah tindakan pencitraan oleh GAM pasca kemunduran militernya, Malik menjawab:
Opini internasional pasca-tsunami juga lebih condong ke dialog damai Helsinki yang dilaksanakan antara pemerintah Indonesia dan GAM. Kedua pihak mengirimkan pejabat tertingginya sebagai negosiator, sementara perwakilan pada dialog "Cessation of Hostilities Agreement" (CoHA) yang ditandatangani bulan Desember 2002 adalah perwakilan yang cenderung masih di tingkat junior.
Para petinggi GAM juga menilai bahwa selama dialog damai Helsinki tidak ada komunitas internasional yang mendukung aspirasi kemerdekaan Aceh. Tentang hal ini, Malik berkata:
Saat menjelaskan kepada para komandan GAM mengenai penerimaan tawaran pemerintahan sendiri alih-alih melanjutkan perjuangan kemerdekaan, para petinggi GAM menegaskan bahwa jika mereka terus memaksa menuntut kemerdekaan setelah tsunami 2004, mereka akan terancam dikucilkan oleh komunitas internasional.