Michael set off towards Macedonia with an army of 40,000 men in 1041, assisted by Norse mercenaries, including the future King Harald III of Norway.
Mikhael, bagaimanapun, kembali dengan pasukan 40.000 orang pada tahun 1041, dibantu oleh tentara bayaran Norse termasuk masa depan Raja Harald III dari Norwegia.