Zgodba o HK Velenje se je posredno začela pred mnogimi leti na Škalskem jezeru v Velenju. Kadar so zime to omogočale, so se lokalni ljubitelji drsanja in hokeja na ledu dobivali na jezeru, ter cele dneve preživljali na ledu. Dobivali so se »stari in mladi« iz Velenja, Škal, Šoštanja, Pesja, Florjana, včasih se je pridružil še kdo iz bolj oddaljene okolice.

Tudi zaradi nevarnosti, ki spremljajo drsanje po naravnih zaledenelih jezerih, so začeli razmišljati o pripravi ledene ploskve na malo-nogometnem igrišču, saj se te prakse že vrsto let s pridom poslužujejo v Florjanu, včasih pa je led obstajal tudi v Velenju na konovskem igrišču in še prej na velenjskem kotalkališču. Tako je skupina prijateljev pozimi 2003/2004, z izdatno pomočjo Športnega društva Škale, škalskih gasilcev in Šaleškega študentskega kluba, uredili ledeno ploskev na igrišču za mali nogomet v Škalah.

Ideja o ustanovitvi kluba se je porodila v začetku decembra 2006. Po pripravi ustreznih aktov društva je bil tako 16. 12. 2006 na ustanovni skupščini rojen Hokejski klub Velenje (HKV), ki je v januarju 2007 z vpisom v razvid društev tudi uradno postal društvo, ki deluje na področju športa.