Sejarah terbentuknya PSIM dimulaipada tanggal 5 September 1929 dengan lahirnya organisasi sepak bolayang diberi nama Perserikatan Sepak Raga Mataram atau disingkat PSM. Nama Mataram digunakan karena Yogyakarta merupakan pusat pemerintahan kerajaan Mataram. Kemudian pada tanggal 27 Juli 1930 nama PSM diubah menjadi Perserikatan Sepak Bola Indonesia Mataram atau disingkat PSIM sebagai akibat tuntutan pergerakan kebangsaan untuk mencapai kemerdekaan Indonesia. PSIM sendiri saat itu sesungguhnya merupakan suatu badan perjuangan bangsa dan Negara Indonesia.
 Pada tanggal 19 April 1930, PSIM bersama dengan VIJ Jakarta, BIVB Bandung, MIVB (sekarang PPSM Magelang), MVB (PSM Madiun) SIVB (Persebaya Surabaya), VVB (Persis Solo) turut membidani kelahiran PSSI dalam pertemuan yang diadakan di Societeit Hadiprojo Yogyakarta. PSIM dalam pertemuan tersebut diwakili oleh HA Hamid, Daslam, dan Amir Noto. Setelah melalui perbagai pertemuan akhirnya disepakati berdirinya organisasi induk yang diberi nama Persatuan Sepak Raga Seluruh Indonesia (PSSI) pada tahun 1931 dan berkedudukan di Mataram
Sejak tahun itu pulalah kompetisi tahunan antar kota/perserikatan diselenggarakan. Dalam kompetisi perserikatan, PSIM pernah menjadi juara pada tahun 1932 setelah dalam pertandingan final di Jakarta mengalahkan VIJ Jakarta. Selanjutnya PSIM berkali-kali hanya dapat menduduki peringkat kedua setelah kalah dalam pertandingan final kompetisi perserikatan pada tahun 1939, 1940, 1941, 1943, dan 1948.
Sejak Liga Indonesia bergulir pada tahun 1994, prestasi PSIM mengalami pasang surut yang ditandai dengan naik turunnya PSIM dari divisi utama ke divisi I Liga Indonesia. PSIM pernah mengalami degradasi pada Liga Indonesia 1994/1995 dan promosi dua tahun kemudian. Setelah bertanding selama tiga musim di divisi utama, PSIM kembali harus terdegradasi ke Divisi I pada musim kompetisi 1999/2000.
Tiga tahun kemudian pada Divisi I Liga Indonesia 2003 PSIM baru bangkit dan membidik target untuk promosi dengan persiapan tim yang matang. Di babak penyisihan PSIM bahkan dua kali mengkandaskan tim favorit Persebaya Surabaya dalam pertandingan tandang kandang dengan skor telak 3-1, dan 3-0, dan menjuarai Grup C. Sayangnya keperkasaan PSIM semakin lama semakin luntur sehingga gagal melanjutkan dominasinya pada babak 8 besar yang berlangsung dengan kompetisi penuh. PSIM yang sejak awal memimpin klasemen harus puas berada di peringkat ke-4, dan berkesempatan untuk mengikuti playoff. Di babak playoff yang dimainkan di Solo, PSIM kalah bersaing dengan Persela Lamongan hanya karena perbedaan jumlah gol.
 Akhirnya, setelah lama berjuang menggapai tiket promosi ke divisi utama, PSIM berhasil meraihnya pada Divisi I Liga Indonesia 2005. Bahkan PSIM berhasil menjadi juara kompetisi setelah menaklukan Persiwa Wamena 2-1 dalam final yang digelar di Stadion Jalak Harupat, Soreang, Bandung, 4 September 2005. Gol kemenangan PSIM ditentukan oleh tendangan penalti yang dieksekusi oleh M.Erwin pada menit ke-49.
PRESTASI
- Liga Indonesia 1994/1995 : Peringkat 17 Wilayah Timur (Degradasi)
- Liga Indonesia 1995/1996 : Divisi I Liga Indonesia 1996/1997 :
Juara Dua Divisi I(Promosi)
- Liga Indonesia 1997/1998 : Peringkat 10 Wilayah Tengah (Liga dihentikan)
- Liga Indonesia 1998/1999 : Peringkat 5 Wilayah Tengah
- Liga Indonesia 1999/2000 : Peringkat 14 Wilayah Timur (Degradasi)
- Liga Indonesia 2001 : Peringkat 3 Grup Tengah I Divisi I
- Liga Indonesia 2002 : Peringkat 5 Grup 2 Divisi I
- Liga Indonesia 2003 : Peringkat 3 Playoff Divisi I
- Liga Indonesia 2004 : Peringkat 6 Wilayah Barat Divisi I
- Liga Indonesia 2005 : Juara Divisi I (Promosi)
- Liga Indonesia 2006 : Mengundukan diri dari kompetisi bersama
PSS Sleman dan Persiba Bantul Karena Jogja terkena Gempa Bumi. | 
*/