Andrej Petrovski commence le cyclisme à l'âge de dix ans dans son pays natal. Il déménage ensuite avec sa famille en Allemagne. Son père est lui-même un entraîneur de cyclisme[3].
En 2015, il remporte le Prix de Cuiseaux, course du calendrier amateur français[5]. La même année, il termine dixième du Tour d'Ankara en Turquie. En cours de saison 2016, il rejoint l'UC Monaco[3]. En , sous les couleurs monégasques, il obtient la médaille de bronze lors des Jeux des petits États d'Europe.
En 2018, il intègre le club allemand 0711/Cycling. Au mois de juin, il est sacré double champion de Macédoine, de la course en ligne et du contre-la-montre.
