Харальд вынужден был покинуть страну после того, как король Олав погиб в битве при Стикластадире. Шестнадцатилетний Харальд спустился по Финскому заливу к Новгороду. Оттуда он перебрался в Киев, где служил Ярославу Мудрому и сражался против кочевников и поляков.

Викинги познакомились с территорией нынешней Украины еще в IX веке. С юга через Черное море туда прибывали арабские купцы. У них было серебро, которое викинги меняли на меха и рабов. Согласно арабскому хронисту Ибн Фадлану, викинги доставляли по рекам рабов хазарским и волжским купцам. В особенности ценились светлокожие и беловолосые славянские рабыни. Купцы, в свою очередь, перепродавали рабов дальше на юг. Как пишет Ибн Фадлан, перед тем, как отдать купцам женщин, викинги напоследок насиловали их.

В 1034 году Харальд отправился за славой в Константинополь. Там девятнадцатилетний охотник за удачей стал наемником. На службе у византийского императора он сражался в Болгарии и на Сицилии и скопил немалое состояние. Помимо вознаграждения от императора, Харальд также обогатился, грабя и разоряя города.

В сагах Харальд предстает как скаредный человек, жаждущий богатства и власти. Он вернулся на Север с якобы магическим флагом, на котором было начертано «Разрушитель». На поле битвы флаг несли впереди Харальда, и он считал его самым дорогим своим богатством. Он должен был даровать Харальду удачу в сражениях.

Очевидно, в 1043 году, в возрасте 28 лет, Харальд вернулся ко двору Ярослава Мудрого в Киев. Он привез с собой сокровища, награбленные за восемь лет походов. Два года спустя он отправился на родину в Норвегию, чтобы потребовать норвежскую корону.

К тому времени Харальд из наемника превратился в военачальника. Скорее всего, именно тогда он и обрел свое прозвище — Суровый. Харальд постоянно совершал набеги на побережье Дании, разоряя поселения. Тогда же он заключил союз с датским правителем Свеном II, и этот союз продлился два года. Вместе Харальд и Свен доплыли до Зеландии, разграбили ее и сожгли дотла, а потом высадились на остров Фюн, и его постигла та же участь. Викинги захватили в плен множество датчанок. Когда речь шла о насилии, для Харальда и Свена национальность жертв не имела никакого значения.

Когда шаткий союз конунгов в итоге распался, с 1040-х по 1060-е годы Харальд продолжал наводить ужас на побережье Дании. В 1049 году он разграбил и сжег дотла датский торговый город Хедебю. В тактике Харальда, основанной на набегах и разрушениях, не было никакого особого геройства. Он не нападал на укрепления и замки и не стремился оккупировать опустошенные им земли. Похоже, что он искал рабов и легкую наживу там, где жили простые земледельцы и рыбаки. Подобная тактика не требовала больших ресурсов и приносила результат. Из-за набегов Свен казался датчанам слабым правителем, которому не хватало сил защитить своих людей.

Гвин Джонс — уэльский специалист по истории и литературе Северной Европы, иронизирует над исландскими скальдами, которые описывают походы викингов в шутливом и возвышенном стиле. Поэты прикладывали все возможные усилия и воображение, чтобы убедить всех остальных в том, что происходившие сражения выглядели торжественно и в них была даже некая доля юмора. Хотя на деле это было не так уж весело: побережья разграбляли, дома сжигали, мужей убивали, а женщин угоняли в рабство. Именно этим Харальд Суровый и занимался на датских берегах. Но он подверг насилию и разграблению собственный народ. «Сага о Харальде Суровом» с гротескным юмором повествует, например, как Харальд пленяет и ведет в оковах на свой драккар дочерей могущественного мужа Торкеля Гейсы, которых освободили лишь после того, как их выкупили. Харальд нередко практиковал шантаж и требовал выкуп. Согласно Гвину Джонсу, походы викингов вообще можно описать как бесконечную и бесцельную борьбу.

Харальд старался укрепить свою власть в Норвегии, в особенности в Тронхейме. Там он решил провести мирные переговоры с местным высокородным воином Эйнаром Тамбарскельфиром.