De naam verwijst naar de Abchazische stad Gagra. De club had een voorganger in Siharuli-90 Gagra uit de stad Gagra, die in 1990 tijdens het uiteenvallen van de Sovjet-Unie opgericht was, nadat de oorspronkelijke club Dinamo Gagra niet in de Georgische maar in de Russische competitie ging spelen. Dinamo werd in 1991 opgeheven. Na de Russisch-Georgische Oorlog (2008) werd Abchazië, waarin Gagra gelegen is, door Rusland erkend als onafhankelijk land en werd in Gagra ook een club onder de naam FK Gagra opgericht die in de Abchazische competitie speelt.
FK Gagra uit Tbilisi speelde van 2008 tot 2010 in de Oemaghlesi Liga, het hoogste niveau in Georgië. In 2011 werd de club kampioen in de Pirveli Liga en promoveerde weer naar het hoogste niveau. De club won dat seizoen ook de Georgische beker en mocht deelnemen aan de UEFA Europa League. In 2012 degradeerde de club. In 2020 veroverde de club opnieuw de Georgische beker en mocht in 2021 deelnemen aan de nieuwe UEFA Europa Conference League.
Besik Chikhradze
