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.
Emil blev närmast helgonförklarad i hemlandet efter att han ensam tog Bulgarien till fotbolls-VM 94 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 91a spelminuten varpå den bulgariska kommentatorn utbrast i det numer klassiska citatet "Gud är bulgar!"
