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