Swoją karierę piłkarską Kostić rozpoczął w klubie FK Radnički 1923 z rodzinnego miasta Kragujevac. W 2009 roku awansował do pierwszego zespołu. 5 sierpnia 2010 zadebiutował w nim w 15 sierpnia 2010 w wygranym 1:0 domowym meczu z FK Novi Sad. W sezonie 2009/2010 wywalczył z Radničkim awans do Super ligi. W Radničkim grał do końca sezonu 2010/2011.
Latem 2011 Kostić przeszedł za kwotę 1,3 miliona euro do holenderskiego FC Groningen. W Eredivisie swój debiut zaliczył 21 października 2012 w przegranym 0:3 wyjazdowym meczu z SC Heerenveen. W sezonie 2013/2014 był podstawowym zawodnikiem Groningen.
W 2013 roku Kostić podpisał kontrakt z niemieckim VfB Stuttgart, który zapłacił za niego kwotę 6 milionów euro. W Stuttgarcie zadebiutował 24 sierpnia 2014 w zremisowanym 1:1 wyjazdowym meczu z Borussią Mönchengladbach. W sezonie 2014/2015 grał w podstawowym składzie Stuttgartu.