Byl vychován v mládežnické akademii Partizanu Bělehrad. Tam se mu ale nepodařilo dostat do A-týmu a tak odešel hostovat do FK Teleoptik. Následně šel v roce 2011 do Itálie, kde o něho projevila zájem ACF Fiorentina a která ho koupila za cca 2,5 milionu €. Zde působil nejprve v mládežnickém týmu. Poté začal trénovat s A-týmem a svůj klubový debut si odbyl 11. září 2011 ve vítězném zápase Fiorentiny proti Bologni (výhra 2:0). Při zápase proti AC Milán Matija ukázal hodně svých vlastností, kdy tento výkon nezůstal ve světě fotbalu nepovšimnut a tak Matija přestoupil do anglického Manchesteru City, kde podepsal pětiletou smlouvu. V Manchesteru si svůj debut odbyl hned v prvním zápase Ligy mistrů proti Realu Madrid. Od ledna 2015 hostoval půl roku v FC Schalke 04,[2]
v létě jej německý celek odkoupil za částku 12 milionů eur.[3]
↑ Barclays Premier League Squad Numbers 2013/14. www.premierleague.com. Premier League, 16 August 2013. Dostupné v archivu pořízeném dne 2013-09-25.Je zde použita šablona {{Cite news}} označená jako k „pouze dočasnému použití“.
↑ Archivovaná kopie. www.profutbal.sk [online]. [cit. 2015-01-13]. Dostupné v archivu pořízeném z originálu dne 2015-03-17.
↑AKERMAN, Nick. Matija Nastasic Transfer Clause Activated by Schalke: Latest Details, Reaction. Bleacher Report [online]. 2015-03-25 [cit. 2020-07-16]. Dostupné online. (anglicky)