1992–2003: In den unteren Ligen

Die Mannschaft aus dem Süden Russlands war nach dem Zusammenbruch der Sowjetunion eines der Gründungsmitglieder der neugeschaffenen russischen Obersten Liga. Nach der enttäuschend verlaufenen Saison 1992 belegte das Team in der Abstiegsrunde den 18. Tabellenplatz und musste in die zweitklassige 1. Division absteigen. In der nächsten Spielzeit folgte der sofortige Abstieg in die 2. Division, wo das Team zwei Saisons verbrachte. Von 1996 bis 1998, als der enttäuschende 20. Tabellenplatz belegt wurde, spielte die Mannschaft erneut zweitklassig. Die nächsten zwei Saisons verbrachte das Team in der drittklassigen 2. Division. Nach dem Aufstieg 2000 gehörte Kuban Krasnodar sofort zu den Spitzenmannschaften der 1. Division. Zunächst wurde 2001 der dritte Tabellenrang erkämpft. 2002 wurde der Verein Dritter. 2003 folgte die Vizemeisterschaft in der 1. Division und der damit verbundene Wiederaufstieg in die Premjer-Liga.

2003–2010: Auf- und Abstiege

Erst in der Saison 2004, nach elfjähriger Abstinenz spielte Kuban Krasnodar wieder erstklassig. Belegte allerdings den vorletzten Tabellenplatz und stieg wieder ab. Nach dem fünften Platz 2005 gewann Kuban Vizemeisterschaft in der 1. Division 2006 und kehrte in die Premjer-Liga zurück. Die Saison 2007 beendete der Verein erneut auf dem vorletzten Tabellenplatz, der zum abermaligen Abstieg führte. 2008 und 2009 wiederholte sich die Geschichte des Auf- bzw. Abstiegs. 2008 wurde die Vizemeisterschaft in der 1. Division gewonnen – Kuban stieg auf. 2009 wurde der enttäuschende vorletzte Tabellenplatz erreicht – Kuban stieg ab. Es folgte der Aufstieg 2010. Der Verein entwickelte sich im 21. Jahrhundert zur russischen Fahrstuhlmannschaft mit sieben Ligawechseln zwischen 2003 und 2010.

2011–2016: Erster Auftritt auf der europäischen Fußballbühne

In der Übergangssaison 2011/12 spielte Kuban wieder erstklassig und erkämpfte den achten Tabellenrang. In der Premjer-Liga 2012/13 wurde der fünfte Tabellenplatz belegt, der zu der erstmaligen Teilnahme an der UEFA Europa League berechtigte. Nach Erfolgen in der dritten Qualifikationsrunde gegen den FC Motherwell, sowie in der Playoff-Runde gegen Feyenoord Rotterdam, scheiterte das Team erst in der Gruppenphase des Wettbewerbs. In der Gruppe A belegte Kuban Krasnodar den dritten Tabellenplatz hinter FC Valencia sowie Swansea City und vor dem FC St. Gallen. 2015 stand Kuban Krasnodar im Finale des nationalen Fußballpokals, das allerdings mit 1:3 nach der Verlängerung gegen den hauptstädtischen Verein Lokomotive Moskau in Astrachan am 21. Mai verloren wurde. 2016 musste der FK Kuban in die Relegation gegen Tom Tomsk, unterlag dem Club aus Westsibirien und stieg nach fünf Spielzeiten in der Premjer-Liga erneut in die zweitklassige 1. Division ab. Im Juni 2016 übernahm erneut der Rumäne Dan Petrescu den Chef-Trainerposten bei Kuban, wurde allerdings bereits am 4. Oktober 2016 wegen anhaltender Erfolglosigkeit entlassen.

Der FK Kuban Krasnodar wurde Mitte 2018 nach Konkurs aufgelöst.