Karijeru je započeo u Radničkom iz Niša. Godine 1986. je prešao u FK Crvena zvezda. Ubrzo je postao kapiten tima i jedan od najboljih fdbalera u Jugoslaviji. Trećeg maja1989. promovisan je u petu Zvezdinu zvezdu. Godine 1990. prešao je u francuski Olimpik iz Marseja sa kojim je već u prvoj sezoni došao do finala Kupa evropskih šampiona u kojem se njegov klub sastao upravo sa Crvenom zvezdom, a Stojković je odigrao svega nekoliko minuta. Iz Olimpika je prešao u Veronu gde je proveo jednu sezonu. Igračku karijeru je završio u Nagoji (Japan). U Japanu je tri puta izabran za najboljeg igrača lige: 1995, 1996. i 1999.
Reprezentacija
Za reprezantaciju Jugoslavije je odigrao 84 utakmice. Debitovao je 1984. u Francuskoj. Učesnik je Svetskog prvenstva 1990. u Italiji, Francuskoj 1998. i Evropskog prvenstva 2000. u Holandiji i Belgiji. Njegov pogodak na Svetskom prvenstvu 1990. protiv Španije stručnjaci su proglasili jednim od 50 najboljih golova Svetskih prvenstava.
U toku fudbalske sezone 2007/08. odlazi ponovo u Japan da bi trenirao Nagoju. U debitantskoj sezoni sa klubom zauzima treće mesto u prvenstvu i biva proglašen za najuspešnijeg trenera u japanskoj Džej ligi.