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 4e eindigde, datzelfde jaar speelde de club ook voor het eerst Europees in de Europacup II. Het Deense Odense BK beëindigde de Europese droom echter al in de voorronde.
De 4e plaats werd herhaald in 1997. Ook Europees deed de club het niet slecht, in het seizoen 2003/04 werd het Macedonische FK Belasica Strumica 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. In het seizoen van 2023/24 wist de club dit kunstje te herhalen en werd voor de tweede maal kampioen van Slovenië.