Op 8 juli 2010 leidde Kostadinov zijn eerste wedstrijd in Europees verband tijdens een wedstrijd tussen Dacia Chisinau en FK Zeta in de eerste voorronde van de UEFA Europa League; het eindigde in 0–0 en de Bulgaar gaf vier gele kaarten en één rode.[1] Zijn eerste interland floot hij op 2 september 2011, toen Andorra met 0–3 verloor van Armenië. Tijdens dit duel gaf Kostadinov twee gele kaarten en een rode aan de Andorrese verdediger Ildefons Lima.[2]
Bulgarije
Andorra – Armenië 