Несколько раз Харальд пробовал свои силы в походах по Восточному Пути (восточному — для норманнов) на саксов, вендов, куронов и другие народы, но Ярослав исподволь направил его устремления в иное русло, желая доставить приятное византийским монархам и соединить его с полезным для себя самого.
В 1038 году варяжский флот прибыл в Константинополь, где тогда правили императрица Зоя и Михаил IV Пафлагонец. Харальд понравился Зое и был принят ею на службу, а вскоре был назначен предводителем всей русско-варяжской дружины. Уже осенью викинги вышли в Эгейское море совместно с византийской флотилией Георгия Маниака на ловлю пиратов: лавры Венеции, очистившей от пиратов Адриатику и уверенно владевшей ею, многих государей лишали тогда душевного равновесия. Однако вскоре между Хараль-дом и Георгием вспыхнуло несогласие, они разделились и стали действовать самостоятельно, дабы показать всем, кто чего стоит.
Харальд отплыл на запад. Его привлекала Страна Сарацин, о несметных ее богатствах он был уже достаточно наслышан. Арабы в это время по уши увязли в Испании, где продолжалась Реконкиста. Как раз в тот год, когда Харальд прибыл к Ярославу, пал Кордовский халифат, и эхо этого падения разнеслось по самым отдаленным закоулкам Европы. Неудивительно поэтому, что норманны не встретили в Стране Сарацин сколько-нибудь серьезного сопротивления. Если верить саге, викинги захватили в Африке восемьдесят городов, а поскольку награбленная добыча их слишком обременяла, они отсылали ее «с верными людьми» к Ярославу. Облегчив казнохранилища африканских властителей, варяги отбыли на Сицилию и овладели там четырьмя крупными городами, считавшимися неприступными. Здесь Харальд проявил незаурядную тактическую изворотливость.
Первый город имел столь прочные стены, что об осаде нечего было и думать. Харальд разбил лагерь у близлежащего леска и стал наблюдать. Вскоре решение было найдено, оно почти ничем не отличалось от решения Ольги у стен Искоростеня. Норманны наловили городских ласточек, то и дело летавших в лес на поиски пищи, привязали к их спинкам сосновые стружки, смазанные воском и серой, подожгли их и отпустили обезумевших птиц к их гнездам. Через очень короткое время пылающий город распахнул свои ворота и запросил пощады.
По-видимому, изобретателями этого способа были датчане. По крайней мере, с датчанами связано самое раннее его упоминание. Саксон Грамматик рассказывает, как его применял легендарный датский герой Хаддинг, сын короля Грама, воспитывавшийся, правда, в Швеции. Хаддинг для датчан — это примерно то же, что Геракл для греков или Эней для римлян, и, разумеется, нельзя слепо принимать на веру все сообщаемое о нем. Невозможно и датировать связанные с ним события, хотя путем довольно сложных и не очень уверенных сопоставлений по ряду обмолвок и деталей можно прийти к выводу, что речь идет о рубеже IX—VIII веков до н. э. (в этом случае Хардинг оказывается современником Ромула). Согласно легендам, во время своих странствий, не уступающих странствиям Геракла, Хаддинг уничтожил некий славянский город Хандван (или Хольмгард, или Дина) в Геллеспонте точно так же, как Ольга и некоторые другие исторически реальные персонажи, при помощи горящей смолы, привязанной к ножкам ласточек. Нельзя, однако, исключать и того, что Саксон приписал Хаддингу в легендарно трансформированном виде подвиг Сигурда, и что «город в Геллеспонте» — это та самая крепость заГеллеспонтом (если бы Сигурд плыл восточным путем) в Сицилии...
Второй город викинги взяли подкопом. Случаю было угодно распорядиться так, что конец этого подкопа оказался как раз под пиршественной залой, где отцы города в этот час весело ублажали свои желудки. Можно себе представить, как на их пищеварение подействовало внезапное появление «из-под земли» вооруженных до зубов головорезов! В считанные минуты ворота были отперты, и в них хлынуло войско викингов, истомившихся ожиданием и жаждой мести.
У третьего города, обнесенного кроме неприступных стен еще и широким рвом, викинги... затеяли игры на равнине, убрав с глаз долой все оружие. Горожане, выставив на стены вооруженных воинов и широко распахнув ворота в упоении своей безнаказанностью, наблюдали за ними несколько дней, осыпая насмешками и оскорблениями. Видя, что ничего страшного не происходит, они осмелели еще больше и стали выходить на стены безоружными, по-прежнему держа ворота открытыми. Это не осталось незамеченным, и однажды викинги вышли на игры в полном вооружении, тщательно замаскировав мечи плащами, а шлемы шляпами. Играя, они все ближе подступали к стенам на глазах беспечных горожан, а когда те спохватились, было поздно. По сигналу Харальда норманны молниеносно обмотали плащами левые руки, в правые взяли мечи и устремились в раскрытые ворота. Этот бой был особенно ожесточенным (Харальда сильно изранили, у него было рассечено лицо), но и этот город пал, как все предыдущие.