* Penampilan dan gol di klub senior hanya dihitung dari liga domestik dan akurat per 7 Oktober 2023 ‡ Penampilan dan gol di tim nasional akurat per 12 September 2023
Lahir di Prilep, SR Makedonia, Yugoslavia, Nestorovski memulai kariernya di klub kota kelahirannya yaitu FK Pobeda. Bergabung dengan akademi muda mereka pada tahun 2000, ia melakukan debut seniornya pada tahun 2006. Antara tahun 2006 dan 2010, ia membuat 96 penampilan liga untuk Pobeda, mencetak 39 gol.
Pada minggu-minggu awal tahun 2010, Nestorovski kemudian pindah ke klub Liga Pertama Ceko, Slovácko. Dia membuat sebelas penampilan di sisa pertandingan musim itu, ia mencetak gol liga pertamanya dan satu-satunya dalam kemenangan 3-1 atas Slavia Prague.[1] Musim berikutnya, ia membuat tujuh belas penampilan, sekali lagi ia mencetak satu gol.
Nestorovski kemudian dipinjamkan ke Viktoria ižkov di mana ia menghabiskan paruh pertama musim 2011–12. Dia meninggalkan klub tersebut pada Januari 2012 dan pindah ke Metalurg Skopje, disana ia menghabiskan dua belas bulan berikutnya dengan klub tersebut.
Setelah tidak bermain selama hampir enam bulan, Nestorovski menandatangani kontrak dengan Inter Zapreši pada 9 Agustus 2013, awalnya dengan status pinjaman. Dia memiliki tahun terobosan, mencetak 20 gol di Liga Kedua Kroasia dan dua kali di Piala Kroasia. Dia memperpanjang kesepakatan pinjamannya dengan Inter selama 12 bulan lagi selama musim panas. Musim berikutnya, Nestorovski menikmati lebih banyak kesuksesan, mencetak 24 gol dalam 27 pertandingan liga saat Inter dipromosikan ke Liga Utama Kroasia. Inter kemudian mengontraknya dengan kontrak permanen.
Setelah mencetak 13 gol di paruh pertama 1. HNL, Nestorovski menandatangani kontrak dengan klub Serie A Italia Palermo, tetapi menghabiskan sisa musim 2015-16 bersama Inter. Inter menerima biaya transfer 500.000 euro sementara pemain menandatangani kontrak empat tahun, mulai Juli 2016.[2] Setelah musim debut dengan sebelas gol dan tiga assist, ia terpilih sebagai kapten setelah memutuskan untuk tinggal di klub terdegradasi Palermo meskipun ia diminati klub seperti Fiorentina dan Everton.
Pada 26 Juli 2019, Nestorovski menandatangani kontrak dengan Udinese, setelah Palermo dikeluarkan dari Serie B.
