W lutym 2008 Krasnodar otrzymał status klubu profesjonalnego i debiutował w Drugiej Dywizji, grupie Południowej, w której zajął trzecie miejsce. Swój pierwszy oficjalny mecz Byki rozegrały przeciwko drużynie FC Nika Krasny Sulin. Spotkanie zakończyło się remisem 0-0. Pierwszy pełny sezon ligowy klub zakończył na trzecim miejscu w tabeli. Pomimo, że klub nie uplasował się na miejscu dającym bezpośredni awans, otrzymał promocje do Rosyjskiej Pierwszej Dywizji na wskutek wycofania się wyżej sklasyfikowanych drużyn.
Po dwóch latach gry na zapleczu najwyżej ligi, drużyna ostatecznie awansowała do Primjer-Ligi. Klub mimo zajęcia piątego miejsca w lidze, otrzymał awans, gdyż wyżej sklasyfikowane druzyny Saturna Ramenskoje, Wołgi Nizhny Novogrod i KAMAZ odmówiły gry w Primjer-Lidze ze względu na problemy finansowe.
Drużyna prowadzona przez Slavoljuba Muslina, pomimo nierównej formy na przestrzeni całego sezonu, zakończyła debiutancki sezon na dziewiątym miejscu. W trakcie rozgrywek miały miejsce pierwsze pierwszoligowe derby Krasnodaru, które zwyciężył FK Krasnodar, pokonując w wyjazdowym spotkaniu (0-1) zespół Kubani Krasnodar.
Kolejny sezon był dla kierownictwa drużyny bardzo rozczarowywujący. W styczniu 2013 klub opuścił najlepszy strzelec ostatniego sezonu, ormianin Yura Movsisyan, dołączając do Spartaka Moskwa. Osłabiona Byki prezentował się znacznie słabiej niż rok wcześniej, co przyczyniło się do zwolnienia szkoleniowca drużyny Slaboljuba Muslina wraz z końcem sezonu.
W sierpniu 2013 roku, nowy renerem drużyny został Białorusin Oleg Kononov. Decyzja ta połączona oraz sprowadzenie do zespołu zawodników o uznanej marce jak Andreas Granqvist, Ari, Artur Jędrzejczyk czy Jurij Gazinski - przyniosła znaczną poprawę w grze zespołu. Sezon 2013-14 był rokrodowy dla drużyny Krasnodaru. Zespół zakończył rozgrywki ligowe na rekordowym piątym miejscu, co umożliwiło Bykom grę w europejskich pucharach w kolejnym sezonie. Ponadto drużyna świetnie spisywała się w Pucharze Rosji, dochodząc do jego finał, który po serii rzutów karnych przegrała z zespołem FK Rostov. Sezon 2014-15, FK Krasnodar zakończył na trzecim miejscu w lidzę, pechowo tracąc drugie miejsce w tabeli, dopiero w ostatniej kolejce. Bykom po raz pierwszy udało się zakwalifkować do fazy grupowej Ligi Europy, pokonując w eliminacjach estoński Sillamäe Kalev, węgierski Diósgyőr i hiszpański Real Sociedad San Sebastian. W fazie grupowej Rosjanie zdobili sześć punktów, które nie przełożyły się na promocję do rundy play-off. W trakcie letniego okna transferowego, zespół wzmocnił Fiodor Smołow, który w barwach klubu dwukrotnie zdobył laur króla strzelców Priemjer-Ligi.
Ta sekcja jest niekompletna. Jeśli możesz, rozbuduj ją.
Od 2009 do 2013 klub swoje domowe spotkania rozgrywał na stadionie Kubań, dzieląc go z lokalnymi rywalami, zespołem Kubani Krasnodar.
W 2012 roku klub zlecił budowę nowego, własnego stadionu, który oficjalnie otwarty został w październiku 2016 spotkaniem reprezentacji Rosji z drużyną Kostartyki (3-4).
Stadion FK Krasnodar
Arena może pomieścić 34 291 ludzi, koszty jej budowy pochłonęły 20 mld rubli.
Q – runda eliminacyjna, 1/16, 1/8, 1/4, 1/2 – odpowiednia faza rozgrywek, Grupa – runda grupowa, 1r gr – pierwsza runda grupowa, 2r gr – druga runda grupowa, F – finał, R – runda, PO – play-off
k. – rzuty karne, los. – losowanie, Dogr. – dogrywka, w. – zasada bramek strzelonych na wyjeździe
Rosja
Sillamäe Kalev
Diósgyőr
Real Sociedad
Lille OSC
VfL Wolfsburg
Everton
Slovan Bratysława
HJK Helsinki
PAOK FC
FK Qəbələ
Sparta Praga
Birkirkara
Partizani Tirana
Red Bull Salzburg
Fenerbahçe SK
Lyngby BK
Crvena zvezda
Standard Liège
FC Porto
FC Basel
