Han spelade VM 1994 och 1998 och EM 1996. Han gjorde ett mycket vackert mål i VM 1998 mot Spanien, vilket också blev Bulgariens enda mål. Kostadinov gjorde 70 landskamper och 26 mål för Bulgarien under åren 1988–1998.
Kostadinov blev närmast helgonförklarad i hemlandet efter att han ensam tog Bulgarien till fotbolls-VM 1994 i USA då han slog in de två målen i den direkt avgörande kvalmatchen på bortaplan mot Frankrike. 2-1-målet sköt han in via ribban i den 91:a spelminuten varpå den bulgariska kommentatorn utbrast i det numer klassiska citatet "Gud är bulgar!"