Gajić begon op zesjarige-leeftijd met voetballen bij Dinamo Pančevo. Hij maakte vervolgens de overstap naar OFK Beograd, waar hij in het seizoen 2013/14 debuteerde in het eerste elftal. Gajić was twee seizoenen lang een vaste waarde in het elftal en speelde 52 wedstrijden waarin hij vijfmaal doel trof.
Op 22 juli 2015 tekende Gajić een contract tot medio 2020 bij Girondins de Bordeaux.[1] Hij maakte zijn debuut voor de club in de Europa League wedstrijd tegen AEK Larnaca op 6 augustus 2015. Hij speelde de volledige wedstrijd.[2] Zijn debuut in de Ligue 1 kwam op 23 augustus 2015 tegen Lille OSC. Hij kwam in zijn eerste seizoen slechts tot negen competitiewedstrijden doordat hij tweede keus was op de rechtsbackpositie achter Youssouf Sabaly.