Seuran perusti vuonna 1957 paikallinen metallurginen kombinaatti nimellä "Severonikel" (suom. "pohjois-nikkeli"), Nimi Montšegorsk-Severonikel otettiin käyttöön vuonna 2000. Vuonna 2009 seura nimettiin pääsponsorin, Norilski nikel-konserniin kuuluvan kaivos- ja metallurgiateollisuusyhtiö Kola MMC:n mukaan (ven. Kolskaja GMK).
Historiansa aluksi Severonikel pelasi paikallisessa sarjassa ja voitti Murmanskin alueen mestaruuksia. Joukkue pelasi ensimmäisen A-kakkossarjan ottelunsa 12. joulukuuta1965 kotonaan HK Trud Krasnogorskia vastaan. Ottelu päättyi vierailijoiden voittoon 1–3. Ensimmäisen ottelunsa korkeimmalla sarjatasolla joukkue pelasi 20. marraskuuta vuonna 1966Vympel Kaliningradia vastaan, jolle se hävisi 1–2. Joukkueen ensimmäisen maalin korkeimmalla sarjatasolla teki Juri Uljanov yhdeksän minuutin peliajan jälkeen. Kaikkiaan joukkue pelasi Neuvostoliiton pääsarjassa seitsemän kauden ajan (1967, 1970, 1971, 1975, 1976, 1991 ja 1992), mutta ei koskaan saavuttanut mitalisijoja. Pääsarjassa se pelasi 189 ottelua, joista saavutti 33 voittoa, 16 tasapeliä ja 140 tappiota maalierolla 454–914. Joukkueen paras maalintekijä korkeimmalla sarjatasolla oli kaikkiaan 98 maalia tehnyt Anatoli Kleimenov. Eniten otteluita pelasi Jevgeni Pavlotšenkov, kaikkiaan 128. Neuvostoliiton toiseksi korkeimmalla sarjatasolla joukkue pelasi 20 kautta, joiden aikana se saavutti 635 ottelussa 400 voittoa, 87 tasapeliä ja 148 tappiota maalierolla 3 010–1 547. Kaikkiaan 14 kertaa se eteni pudotuspeleihin.[2]
Venäjän korkeimmalla sarjatasolla joukkue on pelannut yhteensä seitsemän kautta, 1992–1998 ja viimeksi kaudella 2002-2003. Sen paras sijoitus Venäjän liigassa on kahdeksas sija vuonna 1994. Venäjän toiseksi korkeimmalla sarjatasolla joukkue on pelannut kaudet 1999–2002 ja 2003-2012. Seura on voittanut sarjan mestaruuden kausina 2002, 2006, 2007 ja 2010. Montšegorsk-Severonikel ei ole kuitenkaan halunnut nousta ylemmälle sarjatasolle, mihin sillä olisi ollut mestaruuksien myötä oikeus.[2]
Elokuussa 2012 seuran pääsponsori Kola MMC ilmoitti vaikeassa taloustilanteessaan jääpalloseuralle rahoituksen päättymisestä, mikä ajoi seuran taloudellisiin vaikeuksiin. Taloustilanteen takia Kolskaja GMK ei osallistunut Venäjän mestaruussarjaan kaudella 2012-13.[3]