Proeski je snimio prvi album u 18. godini. On je predstavljao Makedoniju na takmičenju za Pjesmu Evrovizije 2004, iste godine kad je imenovan za ambasadora dobre volje UNICEF-a.
Proeski ilk albümünü 18 yaşındayken çıkarmıştı. 2004 Eurovision şarkı yarışmasında Makedonya'yı temsil eden şarkıcı, aynı yıl UNICEF'in İyi Niyet elçisi seçilmişti.