Kostadinov spillede i årene mellem 1988 og 1998 70 kampe for Bulgariens landshold, hvori han scorede 26 mål. Han deltog blandt andet ved både VM i 1994 og VM i 1998, hvor han i førstnævnte var med til at føre holdet helt frem til semifinalerne. Desuden var han en del af landets trup til EM i 1996.
Kostadinov blev verdensberømt i fodboldverdenen den 17. november1993, da det bulgarske landshold i den sidste kvalifikationskamp til VM i 1994 stod overfor en næsten umulig opgave – da kravet for kvalifikation til slutrunden var en sejr på udebane i Paris over Frankrigs verdensstjerner. Efter at franskmændene havde bragt sig foran, og tingene syntes afklarede, scorede Kostadinov to mål, hvoraf det afgørende til 2-1 blev scoret præcis da måltavlen i Paris viste 89 minutter og 59 sekunder. Bulgarerne var dermed klar til VM, hvor de sluttede som nr. 4, mens franskmændene var ude.