Born in the easternSlavonian city of Vukovar, Croatia, Gajić spent his childhood in the northern Serbian city of Pančevo where he began practicing football at the age of six with Dinamo Pančevo.[3] He was subsequently recruited by OFK Beograd, making his senior debut in the 2013–14 campaign. Afterwards, Gajić was a first team regular for two seasons, collecting 46 league appearances and scoring four goals.
Bordeaux
On 22 July 2015, Gajić signed a five-year contract with French club Bordeaux.[4] His transfer from OFK Beograd reportedly cost Bordeaux €800,000.[5] Initially, Gajić saw little playing time[5] as he was the team's second choice to starting right back Youssouf Sabaly.[3]
Red Star Belgrade
On 4 February 2019, Gajić signed a 3.5-year contract with Red Star Belgrade.[6] Although Red Star qualified for the 2019–20 UEFA Champions League, coach Vladan Milojević and Red Star's management opted not to register Gajić in their 23-man Champions League squad, ultimately choosing Marko Gobeljić as the starting right-back.[7]