Micevski speelde acht interlands (vier goals) voor Macedonië. Onder leiding van bondscoach Andon Dončevski maakte hij zijn debuut voor de nationale ploeg op 13 oktober1993 in de vriendschappelijke uitwedstrijd tegen Slovenië. Hij trad in dat duel, de eerste voor Macedonië als onafhankelijke staat, na 86 minuten aan als vervanger van Zoran Boškovski, de maker van het openingsdoelpunt.