Partai Demokrasi Indonesia Perjuangan (PDI Perjuangan) lahir melalui pertikaian panjang di tubuh PDI yang tak kunjung reda. Puncaknya terjadi pada Kongres PDI 20-21 Juni 1996 di Medan, ketika beberapa anggota pimpinan PDI secara terang-terangan mengabaikan kepemimpinan PDI yang saat itu dipegang oleh Megawati. Kondisi ini kemudian memaksa sebagian pendukung PDI menyelenggarakan Kongres di Bali (Oktober 1998) untuk meneguhkan keberadaan mereka yang ingin berdiri sendiri terpisah dari PDI pimpinan Budi Hardjono. PDI hasil Kongres Bali yang kemudian diketuai oleh Megawati ini akhirnya sepakat menambah kata "Perjuangan" di belakang kata PDI untuk membedakan dengan PDI lainnya.

Seperti yang diamanatkan oleh Kongres V di Bali, maka partai ini bertekad memenangkan Pemilu 1999 serta menunjuk Megawati Soekarnoputri sebagai calon presiden pada sidang umum MPR 1999. Satu hal yang diserukan oleh partai ini adalah terus mempertahankan bentuk negara kesatuan seperti yang dicita-citakan sebelumnya.