Sehari setelah peristiwa bersejarah itu, Pengurus Besar Nahdlatul Ulama (PBNU) mulai kebanjiran usulan dari warga NU di seluruh pelosok tanah air. Usulan yang masuk ke PBNU sangat beragam, ada yang hanya mengusulkan agar PBNU membentuk parpol. Tercatat ada 39 nama parpol yang di usulkan.nama terbanyak yang diusulkan adalah Nahdlatul Ummah, Kebangkitan Umat danKebangkitan Bangsa.
Ada juga yang mengusulkan lambing parpol. Unsure-unsur yang terbanyak diusulkan untuk lambing parpol adalah gambar bumi, bintang Sembilan dan warna hijau, ada yang mengusulkan bentuk hubungan dengan NU, ada yang mengusulkan visi dan misi parpol, AD/ART parpol, ada juga yang mengusulkan semuanya. Di antara yang usulannya paling lengkap adalah Lajnah Sebelas Rembang yang diketuai KH.M.Cholil Bisri dan PWNU Jawa Barat.
Dalam menyikapi usulan yang masuk dari warga nahdliyin, PBNU menanggapinya secara hati-hati. Hal ini didasarkan pada adanya kenyataan bahwa hasil muktamar NU ke-27 di Situbondo yang menetapkan bahwa secara organisatoris NU tidak terkait dengan partai politik manapun dan tidak melakukan kegiatan praktis. Namun demikian, sikap yang ditunjukkan PBNU belum memuaskan keinginan warga NU. Banyak pihak dan kalangan NU dengan tidak sabar bahkan langsung menyatakan berdirinya parpol untuk mewadahi aspirasi politik warga NU setempat. Diantaranya yang sudah mendeklarasikan sebuah parpol adalah Partai Bintang Sembilan di Purwokerto dan Partai Kebangkitan Umat di Cirebon.
Akhirnya PBNU mengadakan rapat harian Syuriyah dan Tanfidziyah PBNU pada tanggal 3 Juni 1998 yang menghasilkan keputusan untuk membentuk Tim Lima yang diberi tugas untuk memenuhi aspirasi warga NU. Tim Lima tersebut diketuai oleh KH.Ma’ruf Amin (Rais Syuriah/Koordinator Harian PBNU), dengan anggota; KH.M.Dawam Anwar (katib Aam PBNU), Dr.KH.Said Aqil Siradj,MA (Wakil Katib Aam PBNU), HM.Rozy Munir, SE,M.Sc (Ketua PBNU), dan Ahmad Bagdja (Sekertaris Jenderal PBNU). Untuk mengatasi hambatan organisatoris, Tim Lima itu dibekali Surat Keputusan PBNU.
Selanjutnya, untuk memperkuat posisi dan kemampuan kerja Tim Lima seiring semakin derasnya usulan warga NU untuk menginginkan partai politik, maka pada rapat harian syuriah dan Tanfidziyah PBNU pada tanggal 20 Juni 1998 memberi Surat Tugas kepada Tim Lima, selain itu juga dibentuk Tim Asistensi yang diketuai oleh Arifin Djunaedi (Wakil Sekjen PBNU) dengan anggota; H.Muhyidin Arusbusman, HM.Fachri Thaha Ma’ruf, Lc, Drs H.Nasihin Hasan, H.Lukman Saifudin, Drs Amin Said Husni dan Muhaimin Iskandar. Tim Asistensi bertugas membantu Tim Lima dalam menginventarisasi dan merangkum usulan yang ingin membentuk parpol baru, dan membantu warga NU dalam melahirkan parpol baru yang dapat mewadahi aspirasi politik warga NU.
Pada tanggal 22 Juni 1998 Tim Lima dan Tim Asitensi mengadakan rapat untuk mendefinisikan dan mengkolaborasikan tugas-tugasnya. Tanggal 26-28 Juni 1998 Tim Lima dan Tim Asistensi mengadakan konsinyering di Villa La Citra Cipanas untuk menyusun rancangan awal menghasilkan lima rancangan, yaitu : Pokok-pokok pikiran NU mengenai reformasi politik, Mabda Siyasiy, Hubungan partai politik dengan NU, AD/ART dan Naskah Deklarasi.
Kemudian pada tanggal 4-5 Juli 1998 diadakan Silaturrahmi Nasional Ulama dan Tokoh warga NU. Dalam kesempatan ini muncul 3 alternatif mengenai nama parpol, yakni Nahdlatul Ummah, Kebangkitan Umat dan Kebangkitan Bangsa.
Berikutnya setelah melalui diskusi verifikasi pada tanggal 17 Juli 1998, dan konsultasi dengan berbagai pihak, Tim Lima dan Tim Asistensi Syuriah dan Tanfidziyah PBNU pada tanggal 22 Juli 1998. rapat tersebut telah menerima rancangan yang disiapkan Tim Lima dan Tim Asistensi untuk diserahkan kepada pengurus parpol sebagai dokumen dan aturan main parpol. Alhasil parpol yang diharapkan dapat menampung aspirasi warga NU pada khususnya dan bangsa Indonesia pada umumnya yang di beri nama Partai Kebangkitan Bangsa, tanggal 23 Juli 1998 bertepatan dengan tanggal 23 Robiul Awal 1419 H di deklarasikan di kediaman KH.Abdurrahman Wahid (Ketua Umum PBNU) di Ciganjur Jakarta Selatan.
Deklaratornya terdiri dari tokoh-tokoh kunci dalam struktur PBNU yaitu: KH.Ilyas Rukhiat (Rois Aam), KH.Munasir Ali, KH Mustofa Bisri dan KH. Abdurrahman Wahid (Gus Dur) selaku Ketua Umum PBNU.
