Впрочем, Вильгельм завоевал Англию не без труда. У этой страны была долгая традиция расовой и культурной гомогенности, пошатнувшейся под тяжелыми ударами датчан, но почти до самого конца поддерживавшейся блестящей династией, Домом Кердика, наследником которой был молодой принц Эдгар. Моркер Нортумберлендский, его брат Эдвин Мерсийский и архиепископ Кентерберийский Стиганд провели формальные выборы и избрали Эдгара королем. Если бы на месте этого молодого человека оказалась одна из его сестер, норманнское завоевание могло и не состояться. Однако Эдгар унаследовал характер скорее Этельреда Унреда, чем Эгберта, Ательстана или Альфреда: он почти сразу же сдался на милость победителя и принес клятву верности Вильгельму, который быстро укреплял свою власть, хотя так до конца и не сумел завладеть Северной Англией.
Когда на следующий год Вильгельм Завоеватель вернулся в Нормандию, Эдгар, Эдвин и Моркер отправились вместе с ним. Впрочем, к весне Эдгар бежал и – возможно, после неудачной попытки поднять восстание – сел на корабль со своей матерью, Агатой Венгерской, и двумя сестрами, Маргаритой и Христиной, намереваясь вернуться в Венгрию. Встречный ветер отнес их корабль в Северное море. Они доплыли до Ферт-оф-Форта и высадились в заливе св. Маргариты, близ Данфермлайна, фактической столицы Малькольма. Там их принял шотландский король и предоставил им убежище. Маргарита была уже взрослой девушкой, отличавшейся необыкновенной красотой, обаянием и умом. Сначала она воспитывалась при дворе св. Стефана, где и познакомилась с византийскими традициями, а затем при дворе св. Эдуарда, все еще поддерживавшем тесные отношения с новым интеллектуальным центром Западной Европы – клюнийской Нормандией. Маргарита выросла мудрой, ученой и святой. Королева Ингеборга умерла, и овдовевший Малькольм тут же влюбился в эту странствующую принцессу. Сначала она отказала ему: она и ее сестра должны были постричься в монахини. Со временем она переменила свое решение, но это произошло только через один или два года.
События того времени носили бурный и не всегда понятный характер. В 1069 г. Вильгельм начал закрепляться на севере Англии, где сильны были легитимистские настроения. Он послал Роберта де Комина (его потомки будут носить в Шотландии имя Коминов) захватить Нортумберленд и Йорк, и из 700 человек, отправившихся с Комином, в живых остался только один. Эдгар присоединился к восставшим, но мятеж был подавлен, а Йорк в наказание был разграблен норманнами. Эдгар предпринял новую попытку, заручившись поддержкой датского флота, и приступом взял Йорк. Однако Вильгельм откупился от датского адмирала и принялся опустошать всю Северную Англию. По всей видимости, Малькольм действовал на стороне Эдгара: он вступил на английскую территорию, обнаружил, что английские легитимисты уже разгромлены, и дошел до Вермута только для того, чтобы убедиться, что сам Эдгар со своей семьей и вождем своих сторонников уже сели на корабль. Согласно Симеону Дюргемскому, Эдгар принес Малькольму вассальную клятву в качестве короля Англии в обмен на предоставленное убежище… А Малькольм получил известие, что Вильгельм передал Нортумберленд, на который он претендовал по праву племянника Сиварда, его кузену Коспатрику, сыну Мальдреда, младшего брата Дункана I, от дочери Ухтреда, ярла Нортумберлендского. И Коспатрик, который поддерживал Эдгара и которого в своем королевстве недавно укрывал от короля Вильгельма Малькольм, начал опустошать Камберленд, на который также претендовал Малькольм. Шотландский король выступил против Коспатрика, разграбил его главную резиденцию в Бамборо и увел в Шотландию так много английских пленников, что, по словам одного английского хрониста, английские рабы появились в каждом шотландском доме. Это был странный способ сватовства к английской принцессе, но в том же 1070 г. Маргарита вышла замуж за Малькольма, и хотя, возможно, она сделала это против своей воли, их брак оказался очень счастливым.
В следующем, 1071 г. Вильгельм двинулся на север, чтобы отомстить шотландцам. Однако Англо-Саксонская Хроникаотмечает, что «он не нашел там ничего, над чем он мог бы владеть», ибо из-за постоянных нашествий саксов, датчан, норманнов и шотландцев несчастная Нортумбрия превратилась в выжженную пустыню. Эдгар даже не попытался оказать Вильгельму сопротивление и бежал во Фландрию. Вильгельм дошел до Файфа, но Малькольм, очевидно, больше не видел никаких оснований ввергать свою страну в новую войну ради шурина, позорно отказавшегося от шотландской поддержки. Он встретился с Вильгельмом в Абернети, где они договорились об условиях мирного договора. Вильгельм согласился выплачивать Малькольму ежегодную субсидию и отдать ему двенадцать английских поместий, которые тот должен был, конечно же, держать в качестве фьефов английской короны. Со своей стороны, Малькольм отослал в заложники своего сына Дункана, тем самым гарантируя выполнение условий соглашения. Из этого договора английские историки в очередной раз извлекли различные домыслы о завоевании Шотландии, однако такая ситуация, когда один государь владел землями в другом королевстве и приносил за них оммаж другому королю, была совершенно обычной для феодальной политики. Сам Вильгельм и все английские короли на протяжении столетий были вассалами французской короны в отношении областей, которыми они владели во Франции, но это не означало сюзеренитета Франции над Англией. Если бы Малькольм стал вассалом Вильгельма в отношении Шотландии, он наверняка призывался бы для несения обычной феодальной службы во время различных последующих войн. Положение вассала у Вильгельма вовсе не означало синекуры. Но шотландская армия никогда не сражалась на его стороне.
Мир дал обоим королям возможность успокоить свои страны. В следующем году Эдгар вернулся в Шотландию с известием, что король Франции предложил ему Монтрей на нормандской границе. Малькольм посоветовал ему принять предложение и обосноваться там, очень щедро наделил Эдгара и его свиту золотой и серебряной посудой, королевскими пурпурными мантиями, подбитыми горностаем, и отправил в плавание, но… через некоторое время они снова явились к его двору, потерпев кораблекрушение. Теперь Малькольм хорошо знал Эдгара, он уже встречался с Вильгельмом и свел личную дружбу с его сыном Робертом. Шотландский король отказался нарушить мир ради беспомощного Эдгара и посоветовал тому покориться. Эдгар послушался и принес Вильгельму клятву верности, за что и получил во владение замок в Нормандии.
Затем начались домашние междоусобицы. Маелснехтайн, сын Лулаха, вырос и, вероятно, заявил о своих притязаниях либо на шотландский трон, либо на звание мормаора Морея, принадлежавшее его деду Гиллекомгану. Во всяком случае, в 1077 г. Малькольму пришлось с ним сразиться. Король выиграл кампанию, однако Маелснехтайну была сохранена жизнь и он дожил до 1085 г. В 1079 г. под угрозой оказался шотландско-английский мир. Вильгельм вступил в Нормандии в войну со своим старшим сыном Робертом, другом Малькольма, а в ответ Малькольм вторгся в Англию. Очевидно, его приветствовала Нортумбрия: во всяком случае, в следующем году Вильгельм направил опустошать эту провинцию епископа Байе. Роберта, с которым Вильгельм уже примирился, он послал грабить Шотландию. Однако тому, по-видимому, претило разорять владения своего друга. Он дошел до Фолкерка, а затем развернулся и двинулся обратно. Впрочем, он построил Ньюкасл на реке Тайн в качестве пограничной крепости вместо утерянного Эдинбурга, тем самым достигнув компромисса между дружбой и сыновьими обязанностями. После этого между Англией и Шотландией вновь воцарился мир, длившийся 14 лет и нарушенный только после смерти Вильгельма. Разразившаяся война оказалась роковой для Малкольма и его супруги.