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ół Kubań Krasnodar.
Kolejny sezon był dla kierownictwa drużyny rozczarowujący. W styczniu 2013 klub opuścił najlepszy strzelec ostatniego sezonu, ormianin Jura Mowsisjan, dołączając do Spartaka Moskwa. Osłabiona drużyna 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.
Nowe otwarcie W sierpniu 2013 roku nowym trenerem drużyny został Rosjanin Oleg Kononow. Decyzja ta połączona ze sprowadzeniem 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/2014 był przełomowym dla klubu z 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łu, który po serii rzutów karnych przegrała z FK Rostów.