Kendati lahir dari keluarga politisi jempolan, sebenarnya, kiprah Mega dalam dunia politik boleh dibilang baru. Tepatnya pada tahun 1987. Ketika itu Partai Demokrasi Indonesia (PDI) sedang mencari orang yang bisa mendongkrak suara. Lalu nama Mega dipasang sebagai salah seorang calon legislatif pada daerah pemilihan Jawa Tengah. Ternyata memang berhasil: PDI naik suaranya, dan Mega "naik" ke Senayan. Ia pun menjadi primadona dalam kampanye PDI. Dan kelihatannya Mega sangat enjoy, meski telah mengingkari kesepakatan keluarganya untuk tidak terjun ke dunia politik. Pada tahun itu pula ia terpilih sebagai Ketua DPC PDI Jakarta Pusat.

Tetapi rupanya, kehadiran Mega di gedung DPR/MPR tidak menjadikannya sebagai primadona, sebagaimana pada masa kampanye. Kinerjanya sebagai anggota dewan dinilai kurang. Ia lebih banyak diam. Bahkan ia jarang datang ke DPR. Namun untuk soal kehadirannya di DPR ini, Mega berdalih bahwa ia lebih banyak melakukan lobi-lobi politik di luar gedung wakil rakyat tersebut.

Bintang Mega sebagai politisi semakin moncer ketika tahun 1993 ia berhasil menjadi Ketua Umum DPP PDI. Proses naiknya Mega ini juga tidak sederhana. Ceritanya, seusai Konggres PDI di Medan yang "mentok" dan tidak menghasilkan keputusan apa-apa, PDI lantas menyelenggarakan Kongres Luar Biasa di Surabaya. Pada kongres inilah Mega ternyata bisa mengungguli kandidat lainnya, Budi Hardjono, yang didukung oleh pemerintah untuk menggantikan Soerjadi.

Singkat kata, Mega akhirnya terpilih sebagai Ketua Umum PDI. Kemudian status Mega sebagai Ketua Umum PDI itu dikuatkan lagi oleh Musyawarah Nasional PDI di Jakarta. Namun dalam perjalanannya, pemerintah tidak puas dengan terpilihnya Mega sebagai Ketua Umum PDI. Karena itu, Mega pun didongkel dalam Kongres Medan tahun 1996. Kongres yang digerakkan oleh Fatimah Ahmad -- salah satu "kabinet Mega" di DPP PDI -- itu menaikkan kembali Soerjadi.