Abdurrahman Wahid
Menjelang Musyawarah Nasional 1994, Gus Dur menominasikan dirinya untuk masa jabatan ketiga. Mendengar hal itu, Soeharto ingin agar Wahid tidak terpilih. Pada minggu-minggu sebelum munas, pendukung Soeharto, seperti Habibie dan Harmoko berkampanye melawan terpilihnya kembali Gus Dur. Ketika musyawarah nasional diadakan, tempat pemilihan dijaga ketat oleh ABRI dalam
tindakan intimidasi. Terdapat juga usaha menyuap anggota NU untuk tidak memilihnya. Namun, Gus Dur tetap terpilih sebagai ketua NU untuk masa jabatan ketiga. Selama masa ini, Gus Dur memulai aliansi politik dengan Megawati Soekarnoputri dari Partai Demokrasi Indonesia (PDI). Megawati yang menggunakan nama ayahnya memiliki popularitas yang besar dan berencana tetap menekan rezim
Soeharto. Wahid menasihati Megawati untuk berhati-hati dan menolak dipilih sebagai Presiden untuk Sidang Umum MPR 1998. Megawati mengacuhkannya dan harus membayar mahal ketika pada Juli 1996 markas PDInya diambil alih oleh pendukung Ketua PDI yang didukung pemerintah, Soerjadi.
Melihat apa yang terjadi terhadap Megawati, Gus Dur berpikir bahwa pilihan terbaiknya sekarang adalah mundur secara politik dengan mendukung pemerintah. Pada November 1996, Wahid dan Soeharto bertemu pertama kalinya sejak pemilihan kembali Gus Dur sebagai ketua NU dan beberapa bulan berikutnya diikuti dengan pertemuan dengan berbagai tokoh pemerintah yang pada tahun 1994 berusaha
menghalangi pemilihan kembali Gus Dur. Pada saat yang sama, Gus Dur membiarkan pilihannya untuk melakukan reformasi tetap terbuka dan pada Desember 1996 bertemu dengan Amien Rais, anggota ICMI yang kritis terhadap kebijakan-kebijakan pemerintah.
Juli 1997 merupakan awal dari Krisis Finansial Asia. Soeharto mulai kehilangan kendali atas situasi tersebut. Gus Dur didorong untuk melakukan reformasi dengan Megawati dan Amien, namun ia terkena stroke pada Januari 1998. Dari rumah sakit, Wahid melihat situasi terus memburuk dengan pemilihan kembali Soeharto sebagai Presiden dan protes mahasiswa yang menyebabkan terjadinya kerusuhan Mei 1998 setelah
penembakan enam mahasiswa di Universitas Trisakti. Pada tanggal 19 Mei 1998, Gus Dur, bersama dengan delapan pemimpin penting dari komunitas Muslim, dipanggil ke kediaman Soeharto. Soeharto memberikan konsep Komite Reformasi yang ia usulkan. Sembilan pemimpin tersebut menolak untuk bergabung dengan Komite Reformasi. Gus Dur memiliki pendirian yang lebih moderat dengan Soeharto dan meminta demonstran berhenti untuk
melihat apakah Soeharto akan menepati janjinya. Hal tersebut tidak disukai Amien, yang merupakan oposisi Soeharto yang paling kritis pada saat itu. Namun, Soeharto mengumumkan pengunduran dirinya pada tanggal 21 Mei 1998. Wakil Presiden Habibie menjadi presiden menggantikan Soeharto.
Salah satu dampak jatuhnya Soeharto adalah pembentukan partai politik baru. Di bawah rezim Soeharto, hanya terdapat tiga partai politik: Golkar, PPP dan PDI. Dengan jatuhnya Soeharto, partai-partai politik mulai terbentuk, dengan yang paling penting adalah Partai Amanat Nasional (PAN) bentukan Amien dan Partai Demokrasi Indonesia-Perjuangan (PDI-P) bentukan Megawati. Pada Juni 1998,
banyak orang dari komunitas NU meminta Gus Dur membentuk partai politik baru. Ia tidak langsung mengimplementasikan ide tersebut. Namun pada Juli 1998 Gus Dur mulai menanggapi ide tersebut karena mendirikan partai politik merupakan satu-satunya cara untuk melawan Golkar dalam pemilihan umum. Wahid menyetujui pembentukan PKB dan menjadi Ketua Dewan Penasihat dengan Matori Abdul Djalil sebagai ketua
partai. Meskipun partai tersebut didominasi anggota NU, Gus Dur menyatakan bahwa partai tersebut terbuka untuk semua orang.
Pada November 1998, dalam pertemuan di Ciganjur, Gus Dur, bersama dengan Megawati, Amien, dan Sultan Hamengkubuwono X kembali menyatakan komitmen mereka untuk reformasi. Pada 7 Februari 1999, PKB secara resmi menyatakan Gus Dur sebagai kandidat pemilihan presiden.
Pada Juni 1999, partai PKB ikut serta dalam arena pemilu legislatif. PKB memenangkan 12% suara dengan PDI-P memenangkan 33% suara. Dengan kemenangan partainya, Megawati diperkirakan akan memenangkan pemilihan presiden pada Sidang Umum MPR. Namun, PDI-P tidak memiliki kursi mayoritas penuh, sehingga membentuk aliansi dengan PKB. Pada Juli, Amien Rais membentuk Poros Tengah, koalisi partai-partai
Muslim. Poros Tengah mulai menominasikan Gus Dur sebagai kandidat ketiga pada pemilihan presiden dan komitmen PKB terhadap PDI-P mulai berubah.
Pada 7 Oktober 1999, Amien dan Poros Tengah secara resmi menyatakan Abdurrahman Wahid sebagai calon presiden. Pada 19 Oktober 1999, MPR menolak pidato pertanggungjawaban Habibie dan ia mundur dari pemilihan presiden. Beberapa saat kemudian, Akbar Tanjung, ketua Golkar dan ketua Dewan Perwakilan Rakyat (DPR) menyatakan Golkar akan mendukung Gus Dur. Pada 20 Oktober 1999, MPR kembali berkumpul dan mulai memilih presiden
baru. Abdurrahman Wahid kemudian terpilih sebagai Presiden Indonesia ke-4 dengan 373 suara, sedangkan Megawati hanya 313 suara.
Tidak senang karena calon mereka gagal memenangkan pemilihan, pendukung Megawati mengamuk dan Gus Dur menyadari bahwa Megawati harus terpilih sebagai wakil presiden. Setelah meyakinkan jenderal Wiranto untuk tidak ikut serta dalam pemilihan wakil presiden dan membuat PKB mendukung Megawati, Gus Dur pun berhasil meyakinkan Megawati untuk ikut serta. Pada 21 Oktober 1999, Megawati ikut serta dalam pemilihan wakil presiden dan mengalahkan Hamzah Haz dari PPP.
Kabinet pertama Gus Dur, Kabinet Persatuan Nasional, adalah kabinet koalisi yang meliputi anggota berbagai partai politik: PDI-P, PKB, Golkar, PPP, PAN, dan Partai Keadilan (PK). Non-partisan dan TNI juga ada dalam kabinet tersebut. Wahid kemudian mulai melakukan dua reformasi pemerintahan. Reformasi pertama adalah membubarkan Departemen Penerangan, senjata
utama rezim Soeharto dalam menguasai media. Reformasi kedua adalah membubarkan Departemen Sosial yang korup.
Pada November 1999, Wahid mengunjungi negara-negara anggota ASEAN, Jepang, Amerika Serikat, Qatar, Kuwait, dan Yordania. Setelah itu, pada bulan Desember, ia mengunjungi Republik Rakyat Tiongkok.
Setelah satu bulan berada dalam Kabinet Persatuan Nasional,Menteri Koordinator Pengentasan Kemiskinan (Menko Taskin) Hamzah Haz mengumumkan pengunduran dirinya pada bulan November. Muncul dugaan bahwa pengunduran dirinya diakibatkan karena Gus Dur menuduh beberapa anggota kabinet melakukan korupsi selama ia masih berada di Amerika Serikat. Beberapa menduga bahwa pengunduran diri Hamzah Haz diakibatkan karena ketidaksenangannya atas pendekatan Gus Dur dengan Israel.
Rencana Gus Dur adalah memberikan Aceh referendum. Namun referendum ini menentukan otonomi dan bukan kemerdekaan seperti referendum Timor Timur. Gus Dur juga ingin mengadopsi pendekatan yang lebih lembut terhadap Aceh dengan mengurangi jumlah personel militer di Negeri Serambi Mekkah tersebut. Pada 30 Desember, Gus Dur mengunjungi Jayapura di provinsi Irian Jaya. Selama kunjungannya, Abdurrahman Wahid berhasil meyakinkan pemimpin-pemimpin Papua bahwa ia mendorong penggunaan nama Papua.
Pada Januari 2000, Gus Dur melakukan perjalanan ke luar negeri lainnya ke Swiss untuk menghadiri Forum Ekonomi Dunia dan mengunjungi Arab Saudi dalam perjalanan pulang menuju Indonesia. Pada Februari, Wahid melakukan perjalanan luar negeri ke Eropa lainnya dengan mengunjungi Inggris, Perancis, Belanda, Jerman, dan Italia. Dalam perjalanan pulang dari Eropa, Gus Dur juga mengunjungi India, Korea Selatan, Thailand, dan Brunei Darussalam. Pada bulan
Maret, Gus Dur mengunjungi Timor Leste. Di bulan April, Wahid mengunjungi Afrika Selatan dalam perjalanan menuju Kuba untuk menghadiri pertemuan G-77, sebelum kembali melewati Kota Meksiko dan Hong Kong. Pada bulan Juni, Wahid sekali lagi mengunjungi Amerika, Jepang, dan Perancis dengan Iran, Pakistan, dan Mesir sebagai tambahan baru ke dalam daftar negara-negara yang dikunjunginya.