Kostadinov va començar la seua carrera a les files del [[CSKA Sofia]], on va formar un destacat trio de grans jugadors amb [[Hristo Stoitxkov]] i [[Liuboslav Penev]] a les darreries de la [[anys 1980|dècada dels 80]]. Amb el CSKA va guanyar tres lligues i tres copes, i va arribar a les semifinals de la Recopa.
AlEl 1990 fitxa pel [[FC Porto]], on s'hi està durant quatre campanyes, tot guanyant la [[lliga portuguesa de futbol|lliga portuguesa]] en dues ocasions. Posteriorment passa pel [[Deportivo de La Corunya]] (sense massa fortuna), [[Bayern de Munic]] (equip amb quiel qual assoleix la [[Copa de la UEFA]] del 96), [[Fenerbahce SK]] i [[UANL Tigres]], on anota 7 gols en 15 partits. Després del seu pas per la lliga mexicana, el rendiment de Kostadinov decau i ja no disputarà de moltsmassa minuts ni al CSKA Sofia ni al 1. FSV Mainz 05, el seu darrer club, alel 1999.
