Coba jelasin Otonomi dan toleransi dari Reformasi Indonesia (1998–sekarang) dong

Gus Dur bermaksud memberikan referendum kepada Provinsi Aceh—yang saat itu memberontak—untuk menentukan model otonomi mereka alih-alih opsi untuk memerdekakan diri seperti di Timor Timur. Gus Dur juga ingin mengambil sikap yang lebih lunak terhadap Aceh dengan menurunkan lebih sedikit personel militer di sana. Pada bulan Maret 1999, pemerintahan Gus Dur mulai membuka negosiasi dengan Gerakan Aceh Merdeka (GAM). Pada bulan Mei, pemerintah menandatangani nota kesepahaman dengan GAM yang berlaku hingga awal 2001, saat kedua belah pihak melanggar perjanjian tersebut.

Pada 30 Desember 1999, Gus Dur mengunjungi Jayapura, ibu kota Provinsi Papua (saat itu disebut "Irian Jaya"). Gus Dur berhasil meyakinkan para pemimpin Papua Barat bahwa dirinya merupakan pemicu perubahan dan bahkan mendorong penggunaan nama Papua.

Pada Maret 2000, Gus Dur menyarankan agar Ketetapan Majelis Permusyawaratan Rakyat Sementara (MPRS) 1966 tentang pelarangan Marxisme–Leninisme dicabut. Pada bulan September, Gus Dur mengumumkan darurat militer di Maluku. Pada bulan yang sama, penduduk Papua Barat mengibarkan bendera Bintang Kejora. Gus Dur menanggapi dengan mengizinkan pengibaran tersebut asalkan bendera Bintang Kejora ditempatkan lebih rendah dari bendera Indonesia. Tanggapan ini dikritik keras oleh Megawati dan Akbar Tanjung. Pada 24 Desember 2000, serangkaian pengeboman dilakukan terhadap gereja-gereja di Jakarta dan delapan kota di seluruh Indonesia.