Ab 2007 gab es erste Bestrebungen, in Krasnodar einen professionellen Eishockeyklub zu gründen. Im Herbst 2011 wurden Vorbereitungen dazu getroffen und der Klub im Frühjahr 2012 ins Vereinsregister eingetragen. Der Name ist analog zum Fußballverein FK Kuban Krasnodar. Zur Saison 2012/13 wurde Kuban Krasnodar als Expansionsteam in die Wysschaja Hockey-Liga, die zweite russische Spielklasse, aufgenommen. Erster Cheftrainer der Vereinsgeschichte wurde Andrei Pjatanow.
HK Kuban Krasnodar fungierte als Farmteam des KHL-TeilnehmersWitjas Tschechow, später des HK Sotschi. Nach der Saison 2014/15 zog sich der Klub aus finanziellen Gründen aus der Wysschaja Hockey-Liga zurück.