Nastasić is een jeugdproduct van FK Partizan Belgrado. Tijdens zijn uitleenbeurt aan FK Teleoptik werd hij opgemerkt door scouts van Fiorentina.
Fiorentina haalde de 18-jarige Nastasić voor 2,5 miljoen euro weg bij Partizan. Aanvankelijk begon hij bij het tweede elftal van Fiorentina maar door blessures bij de andere centrale verdedigers trainde hij meestal mee met het eerste team. Toenmalig Fiorentinacoach en huidig Servisch bondscoach Siniša Mihajlović liet hem debuteren op 11 september 2011 tegen Bologna. Fiorentina won met 2-0. Hij speelde in totaal 26 competitiewedstrijden dat seizoen maar het was vooral één duel dat de aandacht trok van clubs uit zowel binnen- als buitenland. In de wedstrijd tegen AC Milan toonde Nastasić zijn kwaliteiten: harde tackle, rustig aan de bal, tactisch en fysiek erg sterk. Op 31 augustus 2012 contracteerde Manchester City Nastasić voor €15 miljoen + Stefan Savić.
Nastasić tekende een vijfjarig contract bij Manchester City dat hem tot 30 juni 2017 aan de club verbond. Op 18 september 2012 maakte hij zijn debuut voor de club in de Champions League tegen Real Madrid in het Santiago Bernabéu. Aangezien het zijn eerste wedstrijd was in zo'n belangrijk duel, werd het een moeilijke avond voor hem en Vincent Kompany. City verloor met 3-2. Op 29 september maakte Nastasić zijn Premier League-debuut, tegen Fulham.
Manchester City verhuurde Nastasić in de zomer van 2014 voor één seizoen aan FC Schalke 04, dat daarbij een optie tot koop bedong. De club lichtte die optie in maart 2015 en legde de Serviër tot 2019 vast.[1]