Кнут умер в 1035 году, и последовавшая за этим череда смертей унесла всех его сыновей. В результате в Англии в 1042 году на трон вступил король Эдуард, а Дания и Норвегия оказались предоставлены сами себе. Датскую корону получил племянник Кнута по женской линии, Свейн, сын Ульфа, который предпочел именовать себя Свейном Эстридсеном. Властителем Норвегии стал Магнус, сын норвежского короля Олафа Святого, живший до этого в изгнании при дворе новгородского князя Ярослава Мудрого; сокровища из княжеской казны позволили Магнусу изгнать датчан и взять власть в свои руки. Затем он вторгся в Данию и изгнал короля Свейна Эстридсена (как мы помним, в 1047 году Свейн просил помощи в Англии). После этого Магнус правил какое-то время и в Дании, и в Норвегии, что вызывало обоснованную тревогу у короля Эдуарда705.
В 1045 году на сцене появляется новый персонаж — Харальд, сын Сигурда, по прозвищу Суровый, которого называли также Гроза Севера. Некоторые подробности биографии Харальда изложены — кратко и не всегда точно — в хронике, написанной его современником Адамом Бременским706. Гораздо более подробно история его жизни рассказана в Саге о Харальде Суровом, входящей в собрание саг о норвежских королях, составленное в XIII веке исландцем Снорри Стурлуссоном707. Разумеется, саги, записанные спустя двести лет после событий, о которых они повествуют, не могут считаться достоверным историческим источником. Однако в них вкраплены короткие стихотворения, созданные придворными поэтами — скальдами; эти стихи тоже долгое время передавались из уст в уста, но они сложены таким хитроумным способом, что изменить в них — случайно или сознательно — даже одно слово намного труднее, чем в прозаическом тексте. Правда, изощренная композиция, которая препятствует произвольным изменениям текста, порой затрудняет его интерпретацию. В общем, скальдические стихи являются более надежным источником, чем прозаические части саг, но и на них можно опираться только тогда, когда более близкие к событиям источники подтверждают сообщаемые в них сведения.
Харальд Суровый приходился дядей королю Магнусу, правившему Норвегией и Данией. Когда Кнут в 1030 году завоевал Норвегию, Харальд оказался в изгнании, при дворе новгородского князя Ярослава Мудрого. Но, в отличие от Магнуса, который остался на Руси, ожидая возможности вернуться домой (что он и сделал в 1035 году, после смерти Кнута), Харальд отправился в Византию и с 1034 по 1043 год служил там в знаменитой варяжской гвардии. К большой радости историков, этот этап жизни Харальда описан в «Советах и рассказах» византийского писателя Кекавмена (ок. 1020―1080), из которого мы знаем, что Харальд воевал как наемник на Сицилии и в Булгарии и в результате получил повышение по службе. За годы, проведенные в Византии, он приобрел обширный и разноплановый опыт военных кампаний, а также скопил несметные богатства. Благодаря сокровищам, полученным в качестве платы за службу или добытым во время военных походов, Харальд смог (предположительно, в 1044 году) заключить весьма выгодный для себя брак с Елизаветой, дочерью Ярослава Мудрого, и в следующем году вернуться на родину708.
Там Харальд выторговал или отнял у своего племянника часть королевства709, а после смерти Магнуса в 1047 году стал полновластным правителем Норвегии. Исследователи неоднократно отмечали, что в изображениях на скандинавских монетах этого периода явственно прослеживается византийское влияние; по всей видимости, образцами служили разошедшиеся по всему региону византийские монеты из сокровищницы Харальда710. Харальд, несомненно, посчитал, что унаследовал — как преемник Магнуса — и Данию, и попытался прибрать ее к рукам. В результате он на шестнадцать лет оказался втянут в жестокую войну со Свейном Эстридсеном, который в сумятице, последовавшей за смертью Магнуса, сумел вернуться в свое королевство. Харальд выигрывал почти все битвы; в 1050 году он сжег главный торговый город Дании — Хедебю, а также церкви в Орхусе и Шлезвиге. Однако Свейн остался жив, и норвежскому королю так и не удалось подчинить всю Данию себе. Тем временем богатства, накопленные в Византии, иссякли, а трофеев, добытых в победоносных походах в Данию, не хватало на то, чтобы восполнить затраты. Если в первых скальдических стихах из Саги о Харальде Суровом постоянно упоминается о сокровищах, привезенных из Константинополя, то в поэмах, относящихся к периоду после войны со Свейном, таких отсылок практически нет. Монеты Харальда 1060-х годов существенно грубее и хуже качеством, чем те, которые были отчеканены в начале его правления. Утверждение Адама Бременского, что Харальд якобы ограбил могилу своего сводного брата Олафа Святого в Трондхейме711, и сохранившееся письмо папы Александра II, порицающего Харальда за торговлю епископскими кафедрами, косвенным образом подтверждают, что норвежский король испытывал нужду в деньгах. В 1064 году долгая война со Свейном завершилась заключением довольно расплывчатого мирного договора, и Харальду нужно было найти ресурсы для поддержания своей власти в Норвегии. Предложение не заставило себя ждать.