Harald Hardrada, after a few years in Kievan Rus', had moved on south with his force of around five hundred men men to Constantinople (Miklagard), the capital of the Byzantine Empire, probably in 1033 or 1034, where they have joined the Varangian Guard.

Although the Flateyjarbók maintains that Harald at first sought to keep his royal identity a secret, most sources agree that the reputation of Harald and his men was well known in the east at the time.

While the Varangian Guard was primarily meant to function as the emperor's bodyguard, Harald was found fighting on "nearly every frontier" of the empire.

He had first seen action in campaigns against Arab pirates in the Mediterranean, and then in inland towns in Asia Minor that had supported the pirates.

By this time, he had according to Snorri Sturluson become the "leader over all the Varangians".

The Greeks had pushed the Arabs out of Asia Minor by 1035, and Harald had taken part in campaigns that went as far east as the Euphrates, where according to his skald Þjóðólfr Arnórsson (recounted in the sagas) he had participated in the capture of eighty Arab strongholds.

Although not holding independent command of an army as the sagas imply, it is not unlikely that Harald and the Varangians at times could have been sent off to capture a castle or town.

During the first four years of the reign of Emperor Michael IV, Harald probably also fought in campaigns against the Pechenegs.

Harald is reported in the sagas to have gone to Jerusalem and fought in battles in the area; the sagas place this after his expedition to Sicily.

Whether his trip was of a military or peaceful nature would depend on whether it took place before or after the 1036 peace treaty between Michael IV and the Fatimid Caliph Ma'ad al-Mustansir Billah (in reality the Caliph's mother, originally a Greek Christian, since the Caliph is a minor), although it is considered unlikely to have been made before.

Modern historians have speculated that Harald may have been in a party sent to escort pilgrims to Jerusalem (possibly including members of the Imperial family) following the peace agreement, as it was also agreed that the Greeks were allowed to repair the Church of the Holy Sepulchre.

Furthermore, this may in turn have presented Harald with opportunities to fight against bandits who preyed on Christian pilgrims.