По свидетельству Катакалона Кекавмена, в 1034/35 году Харальд во главе варяжского отряда в 500 воинов отправился в Константинополь, который викинги называли Миклагард[88]
. Если общая численность варяжской гвардии в 989 году, в период войны против Варды Фоки, достигала 6000 воинов, то по мнению Г. Г. Литаврина и других исследователей, во второй четверти XI века численность гвардии должна была только увеличиваться[89]. Прибыв в столицу Византийской империи, Харальд уплатил полагающийся взнос и был зачислен вместе с дружиной в ряды варяжской гвардии. Как рассказывает Кекавмен, Харальд, будучи юношей, хотел преклонить колена перед императором Михаилом IV Пафлагонянином и «увидеть ромейские порядки». В «Саге о Харальде Суровом» сказано, что Харальд прибыл в Константинополь в правление императрицы Зои и Михаила V Калафата, т. е. в 1042 году, однако свидетельства Кекавмена заслуживают несравненно большего доверия, поскольку Кекавмен – современник и участник событий. Он мог сражаться вместе с Харальдом против восставших болгар и, вероятно, лично знал его, в то время как скандинавские саги – источник поздний и ненадежный, в силу особенностей жанра скальдической поэзии.Как полагает Т. Н. Джаксон, дальнейшая биография Харальда, вошедшая в сагу «Гнилая кожа» и в некоторые другие предания скальдов, была создана на основе воспоминаний Халльдора Сноррасона, служившего вместе с Харальдом[90]
. Вначале осенью 1034 года Харальд Сигурдсон вместе со своим отрядом воевал против арабских пиратов в Эгейском море. Затем в 1035–1036 годах он участвовал в походе варяжской гвардии в Сирию и Месопотамию, где воевал против местных арабских эмиров. Если сведения скальда Стува Слепого, жившего в XI веке, правдивы, то Харальд с отрядом предпринял в этот период поход в Иерусалим – вероятно, охраняя знатных византийских паломников, – поклонился Гробу Господню и Древу Животворящего Креста, а затем добрался до Иордана. В 1036–1040 и в 1041–1042 годах Харальд принимал участие в боевых действиях на Сицилии в составе полевой армии Георгия Маниака, где отличился при взятии арабской крепости. Крепость удалось поджечь при помощи птиц, к которым привязывали горючие материалы. Исходя из сообщения саг, в ходе войны с арабами Харальд со своим отрядом, действуя в составе варяжской гвардии, предпринимал высадку десанта на побережье северной Африки, т. е. на территории, подконтрольной халифату Фатимидов. Халифат Фатимидов, начиная с периода правления Никифора II Фоки и Иоанна I Цимисхия, был главным противником Византийской империи в восточном Средиземноморье. Борьба против арабского эмирата на Сицилии рассматривалась в Константинополе в качестве одного из театров большой войны с Фатимидами, поэтому использование на Сицилии лучших частей византийской армии, в частности, варяжской гвардии, было в этот период совершенно оправданно. Весной 1041 года Харальд воевал в южной Италии против французских норманнов.После завершения кампании на Сицилии и в южной Италии Харальд осенью 1041 года участвовал вместе с Катакалоном Кекавменом в походе против восставших болгар. Причем, как повествуют саги, Харальд лично убил Петра Деляна – лидера мятежа, за что «удостоился» от скальдов мрачного титула «губитель болгар». По сообщению немецкого хрониста Адама Бременского, Харальд, ставший солдатом императора (miles imperatoris), принимал участие в боевых действиях против сарацин на море и против «скифов» на суше (multa prelia contra Sarracenos in mari et Scitas in terra gessit)[91]
. Вполне вероятно, что Адам Бременский, как современник событий, знал какие-то сочинения скальдов, не дошедшие до нас, где описывалось участие Харальда в боевых действиях варяжской гвардии против печенегов.