Instagram.com/sulselfootballhistory
Saat Perserikatan dan Galatama dilebur menjadi Ligina pada 1994/95, langkah PSM acapkali kandas di babak kedua kompetisi. Padahal mereka tampil garang sepanjang babak penyisihan Wilayah Timur. Predikat runner-up musim 1995/96, di mana mereka kalah 0-2 dari Mastrans Bandung Raya, jadi prestasi maksimal.
Milenium baru ternyata memberi berkah. Finis sebagai pemuncak klasemen Wilayah Barat, kedigdayaan PSM yang waktu diasuh duet pelatih Henk Wullems - Syamsuddin Umar berlanjut hingga Babak 8 Besar. Langkah mereka tak terbendung, Persija ditekuk 1-0 di semifinal, sebelum menundukkan perlawanan PKT Bontang di laga pamungkas. Berkat kemenangan 3-2, Bima Sakti cs kembali menambah item dalam lemari trofi.
Selanjutnya, PSM lagi-lagi harus lebih banyak puas dengan status juara dua tepatnya di musim 2001 (kalah 2-3 dari Persija di final), 2003 (beda 5 poin dengan Persik Kediri), 2004 (beda selisih gol dengan Persebaya).
Format kasta tertinggi kembali berubah, kali ini menjadi Liga Super dengan format satu wilayah. Sayang, PSM konsisten menjadi klub papan tengah. Tahun 2011 mereka melakukan tindakan ekstrim : keluar dari Liga Super untuk menyeberang ke Liga Primer, kompetisi tandingan yang digagas pengusaha Arifin Panigoro
PSM mampu finis di peringkat 3 dibawah juara Persebaya 1927 dan runner-up Persema Malang.