Sebagai tim yang baru terbentuk, PSS mampu membuktikan kualitas yang dimiliki anak-anak Sleman dalam turnamen itu. Mereka keluar sebagai runnerup setelah kalah dari Persiba Bantul di partai final.
Tahun 1979 menjadi awal PSS bermain dalam kompetisi perserikatan, mereka bermain di Divisi II regional DIY dan bertanding dengan tim-tim sepak bola asal Yogyakarta yaitu Persiba Bantul, Persig Gunung Kidul, dan Persikup Kulon Progo untuk lolos ke fase selanjutnya. Mereka mampu menjadi juara dibabak penyisihan regional, namun selalu gagal menembus babak ketiga (tingkat nasional) setelah kalah bersaing dari tim kuat asal Jawa Tengah seperti PSIR Rembang, Persijap Jepara, dan Persibat Batang difase kedua.
Lama berkutat dikompetisi regional DIY, akhirnya pada musim 1994/1995, PSS bisa merasakan bermain di Divisi II Liga Indonesia. Mereka menatap musim itu bermodal skuat seadannya, dan dengan anggaran yang pas-pasan hasil dari donasi para pengusaha yang gila bola di wilayah Sleman. Naman dengan semangat tinggi, tim ini mampu menembus babak 16 besar.
Setahun berselang, dibawah asuhan pelatih Suwarno mereka bisa memastikan satu tiket promosi ke Divisi I. Keberhasilan mereka promosi dimusim 1995/1996 itu tidak mudah harus dilalui lewat pertandingan playoff, bersaing dengan Persiss Sorong, Aceh Putra, dan Persipal Palu.
Lima tahun setelahnya, tepatnya pada musim 1999/2000 menjadi musim yang bersejarah bagi tim ini. Laskar Sembada dibawah asuhan duet pelatih Drs. Bambang Nurdjoko dan Drs. Herwin Sjahruddin berhasil memastikan diri promosi ke Divisi Utama dengan status runnerup Divisi I.
Baca Juga: Cerita Si Cantik Ayu Sriartha Berjuang Jadi Pebasket Profesional
Kesuksean masuk ke Divisi Utama musim itu bak mengobati kekecewaan tim pada musim sebelumnya yang hanya mampu menjadi semifinalis. Capaian mereka musim 1999/2000 semakin terasa manis dengan dinobatkannya mesin gol andalan tim, M. Eksan sebagai top skor.
Pada Divisi Utama musim 2001, mereka tergabung di Grup Timur bersama tim-tim kuat seperti PSM Makasar, Persipura, Persebaya, dan Arema Malang. Di bawah asuhan pelatih Alm. Suharno, pada musim itu PSS mampu menempati posisi 10 diklasemen akhir. Di musim 2002, dengan materi tim ysng hampirsama mereka mampu memperbaiki prestasi dengan duduk diposisi 7 klasemen Grup Timur.
Musim 2003 dan 2004 bisa dibilang menjadi tahun paling bersejarah bagi PSS Sleman di kancah nasional. Dua musim beruntun mereka mampu menempati posisi 4 Divisi Utama dibawah asuhan pelatih Yudi Suryata (2003) dan Daniel Roekito (2004).
Divisi Utama 2005 masih ditangani Daniel Roekito, tim ini tergabung di Wilayah Barat bersama Persija, PSIS, Arema dan PSMS dan mampu menempati posisi 7 di akhir musim. Di tahun tersebut PSS meraih prestasi yang lebih mentereng pada ajang Piala Indonesia atau Copa Dji Sam Soe dengan menjadi semifinalis.
Baca Juga: Zahra Muzdalifah: RA Kartini Sosok yang Menginspirasi Para Wanita di Indonesia
Musim 2006 PSS terpaksa memutuskan berhenti dari kompetisi karena saat itu terjadi bencana gempa bumi yang melanda DIY dan sekitarnya. Atas pertimbangan kemanusiaan, sokongan dana APBD kepada klub dihentikan dan dialokasikan untuk membantu korban bencana.
Pada musim 2007 PSS mencoba bangkit dengan mengusung target masuk ke Liga Super, Liga yang nantinya akan menjadi kompetisi paling bergengsi di Indonesia. Di musim tersebut 9 tim terbaik dari setiap wilayah akan mengisi tempat di Liga Super, namun Super Elang Jawa gagal memenuhi ambisi karena hanya mampu menempati posisi 12 Wliayah Barat.
PSS mampu menjuarai kompetisi Divisi Utama LPIS pada musim 2013, ini menjadi trofi pertamanya sejak didirikan pada tahun 1976. Namun gelar juara itu serasa tidak berarti, pasalnya mereka tidak mendapat tiket promosi dimusim berikutnya karena adanya penyatuan liga.
Mencoba kembali ke panggung teratas, PSS justru pernah terjerat skandal 'sepak bola gajah' saat menjalani pertandingan 8 besar Divisi Utama musim 2014, peristiwa ini mencoreng sepak bola nasional dan menjadi sorotan media internasional. Saat itu mereka yang bertemu dengan PSIS Semarang sama-sama tidak mau menang lantaran sudah ditunggu oleh Borneo FC yang notabene adalah tim kuat. Alhasil kedua tim sama-sama berlomba mencetak gol ke gawang sendiri.