Born in Macedonian capital Skopje, Kostadinov made his professional debut by playing in neighboring Serbia, with FK Moravac Mrštane in the 2014–15 Serbian First League, Serbian second level.
Sinh ra ở thủ đô của Macedonia Skopje, Kostadinov ra mắt chuyên nghiệp bằng việc thi đấu ở đất nước láng giềng Serbia, cùng với FK Moravac Mrštane ở Serbian First League 2014–15, giải hạng hai Serbia.