El nuevo club se formó como FC Gagra en el 2004 en la Regionuli Liga, donde el club logró el ascenso a la Pirveli Liga.
El Gagra perdió en los periodos de 2005-06, 2006–07, 2007-08 los ascensos, ay no pudo jugar en la Umaglesi Liga. Pero después que el original campeón de la Pirveli Liga, el FC Magharoeli Chiatura se retirara, Gagra tomó su lugar. Gagra ganó la primera Liga en la temporada 2010-2011, y se convirtió en el ganador de la Copa, al derrotar en tres ocasiones al FC Torpedo Kutaisi 1-0 en la prórroga.