Začetki rokometa v Slovenj Gradcu segajo v leto 1954. Janez Grabec je skupaj s prijatelji razmišljal, da bi se lahko ta zanimiva igra igrala tudi v Slovenj Gradcu. Na telovadišču Partizana so s kredo zarisali rokometno igrišče in gol. Pričela se je razvijati zgodba, ki je močno zaznamovala Slovenj Gradec v minulih 60 letih. Rokometni navdušenci, ki jih je bilo iz dneva v dan več, so z velikim veseljem spremljali rokometaše in od njih pričakovali vedno več. Ko vodilni v TVD Partizan niso bili najbolj navdušeni nad sekcijo rokometašev, je vodenje prevzel Jože Levovnik in tako postal prvi predsednik slovenjgraških rokometašev. Odločitev o ustanovitvi rokometnega kluba se je izkazala za zelo koristno.

Leta 1958 je slovenjgraški partizan postal prvak koroške rokometne podzveze, velik uspeh pa so rokometaši dosegli tudi v pokalu Jugoslavije, kjer se je članska ekipa uvrstila med 32 najboljših ekip v takratni državi. V letu 1961 so v Slovenj Gradcu pričeli z gradnjo rokometnega stadiona, ki je postal eno izmed najlepših rokometnih igrišč. Igrišče je bilo zgrajeno s prostovoljnim delom igralcev, funkcionarjev in navijačev.

V letu 1961 je bil Slovenj Gradec ponovno okrajni prvak in RZS mu je zaupala izvedbo kvalifikacij za preboj v republiško ligo. Slovenjgradčani so bili na turnirju daleč najboljši in so se po zmagah nad ekipami Rudarja, Velenja, Krmelj in Beltincev prebili v republiško ligo. V letu 1963 so rokometaši Slovenj Gradca kot novinci v ligi postali slovenski prvaki. V finalni tekmi so po porazu v Ljubljani in zmagi v Slovenj Gradcu 3 odločilno tekmo s Slovanom igrali na nevtralnem igrišču v Celju. Na tekmi je bilo kar 500 gledalcev iz Slovenj Gradca, ki so videli veliko zmago svojih ljubljencev.

V letu 1965 je bil slovenjgraški Partizan slovenski podprvak, naslednje leto pa ponovno prvak. V letu 1965 je naslov republiškega prvaka osvojila Slovenjgraška mladinska ekipa. Leta 1967 so Slovenjgradčani osvojili tudi pokal Slovenije. Leta 1971 se je jim je uspelo uvrstiti tudi v zvezno ligo.

V letu 1975 se je pričela graditi športna dvorana, takrat ena najlepših in najsodobnejših v Sloveniji. Športna dvorana je po vseh zapletih z gradnjo vrata odprla novembra 1977. Ob otvoritvi so Slovenjgradčani odigrali tekmo finala pokala Slovenije s Celjem. Zmago so dosegli Celjani. Ob tem dogodku je imela reportažo iz športne dvorane tudi slovenska nacionalna televizija. V letu 1977 so slovenjgraški rokometaši še četrtič postali republiški prvaki. V letu 1977 je v Slovenj Gradec prišel prvi poklicni trener Niko Markovič. Leta 1981 je klub zapustilo veliko igralcev in na vidiku je bila največja kriza v zgodovini takratnega Partizana. V letu 1982 mlada ekipa ni vzdržala močne konkurence v 1 ligi in je iz nje izpadla. To je bilo za rokomet v Slovenj Gradcu izjemno tragično a hkrati priložnost za nove generacije. Rokomet v Slovenj Gradcu kljub črnim napovedim ni ugasnil in prva iskrica pri poti navzgor je bil naslov slovenskih prvakov pri pionirjih leta 1981.

Leta 1985 je člane nazaj v republiško ligo pripeljal Mirko Ogrizek. V letu 1985 so mladinci osvojili naslov republiških prvakov, na klubskem prvenstvu Jugoslavije pa so osvojili 2 mesto. Po 3 letih igranja v republiški ligi je leta 1988 Slovenj Gradec ponovno postal republiški prvak. Leta 1990 je bil Slovenj Gradec že šestič republiški prvak. V letu 1991 je klub uspel dobiti sponzorja. To vlogo je prevzelo podjetje Nova oprema. V sezoni 1992-93 je Nova oprema v slovenskem prvenstvu osvojila 3 mesto in zaigrala v novem tekmovanju EHF v Pokalu mest. V letu 1994 je pokroviteljstvo kluba prevzelo podjetje Prevent. V letu 1994 je Prevent spet prišel v finale Pokala Slovenije in po podaljških so tekmo v Slovenj Gradcu dobili Celjani. V jeseni 1994 je Prevent angažiral prvega tujca Gorana Sokoloviča iz Srbije. V sezoni 1995-96 je v Slovenj Gradec prišel Nenad Maksič vrsto let najboljši strelec slovenske lige. V teh letih so zelo dobro delale tudi mlajše selekcije.