2003–04 წლებში გუნდი, რომელიც შემდეგ გაგრის სახელით გამოვიდა, ჭაბუკთა ლიგაში ასპარეზობდა ლოკომოტივის სახელით. კლუბი 1985–86 წლებში დაბადებული ახალგაზრდებით იყო დაკომპლექტებული. სწორედ ამ წელს უეფამ პირველად ჩაატარა ჭაბუკთა ლიგა საქართველოში და კლუბმა გამოსვლა ჩემპიონობით დაასრულა. საფეხბურთო კლუბ გაგრის ჩამოყალიბების იდეა უკვე არსებობდა. იდეა ეკუთვნოდა უკრაინაში მოღვაწე ქართველ ბიზნესმენ ბესო ჩიხრაძეს. 2004 წელს, ივლისში დღის წესრიგში დადგა კლუბის სახელწოდების საკითხი. გუნდს დაერქვა გაგრა, რადგან პრეზიდენტი ბესო ჩიხრაძე წარმოშობით გაგრიდან იყო.
პირველ ლიგაში გაგრა ცხრილის ზედა ნაწილში დამკვიდრდა, მაგრამ უმაღლესში გადასვლას ვერ ახერხებდა. 2007 წელს გაგრა ფლეი-ოფში დამარცხდა საჩხერის ჩიხურასთან, 2008 წელს – ცხინვალის სპარტაკთან, მაგრამ გამომდინარე იქიდან, რომ პირველი ლიგის გამარჯვებულ "ჭიათურას" არ აღმოაჩნდა მყარი ფინასური გარანტიები, მის ნაცვლად უმაღლეს ლიგაში გაგრა გადავიდა. გუნდმა პირველივე მატჩი სენსაციით დაიწყო, მან მოქმედი ჩემპიონი თბილისის დინამო დაამარცხა. გაგრამ უმაღლეს ლიგაში ორი სეზონი გაატარა და შემდეგ პირველ ლიგაში დაქვეითდა. 2011 წლის სეზონი გუნდმა კარგად ჩაატარა, მოიგო პირველი ლიგა და გახდა საქართველოს თასის გამარჯვებული, დაამარცხა რა ფინალში "ტორპედო ქუთაისი".
კლუბს ჰყავს დუბლშემადგენლობა და ასაკობრივი ნაკრებები 1991-92, 1993-94, 1995-96 წლებში დაბადებული ფეხბურთელებისთვის. კლუბს აქვს ახალგაზრდული ფეხბურთის განვითარების საკუთარი პროგრამა.
ბესო ჩიხრაძე
ნიგერია