De club werd in 1919 opgericht als SSK Celje en nam in 1991 de huidige naam aan. Dat jaar was de club ook medeoprichter van de Sloveense nationale competitie. Slovenië was net onafhankelijk geworden van Joegoslavië. Het eerste succes kwam er in 1993/94 toen de club als 4de eindigde, datzelfde jaar speelde de club ook voor het eerst Europees in de Europacup II. Het Deense Odense beëindigde de Europese droom echter al in de voorronde.
De 4de plaats werd herhaald in 1997. Ook Europees deed de club het niet slecht, in het seizoen 2003/04 werd het Macedonische Belasica weggeveegd en speelde de club gelijk tegen Maccabi Haifa. In 2005/06 won de club de heenwedstrijd van Levski Sofia, maar bij de terugwedstrijd moest het in het zand bijten. In het seizoen 2019/20 werd de club voor het eerst in haar historie landskampioen. Men eindigde het seizoen met 69 punten uit 36 wedstrijden, twee meer dan achtervolgers Olimpija Ljubljana en NK Maribor.