На протяжении почти всей последней трети долгого правления Малькольма — по крайней мере, в течение 12 лет начиная с 1079 г. — Шотландское королевство не испытывало тягот внешних или внутренних войн. Малькольм установил на родине твердое правление и сохранял мир, который он заключил с Вильгельмом Завоевателем. Тем временем английский государь состарился, и все говорило о том, что после его смерти корона перейдет не к его старшему сыну Роберту, другу Малькольма, а к другому сыну Вильгельма, вспыльчивому и сварливому человеку, который обещал стать очень беспокойным соседом. Скорее всего, предвидя возможность будущих трений, Малькольм начал переговоры, о заключении брака своей старшей дочери с герцогом Аланом Бретонским, чтобы заручиться поддержкой Бретани и Нормандии (герцогом которой должен был стать его друг Роберт) в случае войны с Англией.
В 1087 г. Вильгельм Завоеватель погиб ужасной смертью и оставил трех своих сыновей в пылу жестокой ссоры, которая тут же переросла в войну. Королем Англии стал Вильгельм II, но в 1091 г. братья заключили мир и в рамках этого договора изгнали несчастного Эдгара, уже давно спокойно жившего в Нормандии. Как обычно, он прибыл к своему шурину. Малькольм сам имел повод для недовольства Вильгельмом II, который, по-видимому, отозвал дарованные его отцом английские имения. Он набрал армию и напал на Англию. Роберт и Вильгельм II предприняли ответное нападение, причем их войско несло тяжелые потери из-за плохой погоды. Малькольм двинулся им навстречу, но Роберт и Эдгар начали переговоры и задумали принудить двух королей заключить мир и возобновить договор, заключенный некогда в Абернети. Позднее английские хронисты утверждали, что Малькольм, «охваченный ужасом», принес Вильгельму II оммаж за свое королевство. Хронисты же того времени отмечают лишь то, что Малькольм «стал человеком Вильгельма, подчинившись ему в том же, что прежде дал ему отец Вильгельма» (Williames man weano to eall swilce ge-hyrsumnisse swa he г his fder dyde), то есть ему были возвращены владения в Англии и он принес за них оммаж. Жалобы Эдгара также было обещано удовлетворить, и он поехал на юг в качестве гостя Вильгельма II… а через несколько недель Вильгельм II нарушил столько обещаний, что Эдгар и Роберт в негодовании покинули его двор.
Похоже, договоренности с Малькольмом также не были выполнены. По крайней мере, между двумя дворами вновь возникли напряженные отношения, а Вильгельм II отстроил и укрепил Карлайл, который долгое время представлял собой «разоренную область», и направил туда новых, зачастую вынужденных, переселенцев. И с той поры на протяжении более пяти веков этот город и основанный Робертом Ньюкасл оставались главными твердынями и стражами английской границы. Однако весной 1093 г. Вильгельм II серьезно заболел и, почувствовав дыхание адского пламени, не на шутку встревожился. Он решил, что для обеспечения своего потустороннего будущего было бы лучше сдержать данные обещания, и пригласил Малькольма навестить его в Глостере, выдав в качестве гарантий безопасности заложников и послав Эдгара с королевской свитой встретить шотландского государя. Малькольм поехал в Глостер, но не спеша, так как ему было уже за шестьдесят. В пути он сделал остановку, чтобы заложить Даремский собор. В Глостер он приехал только в августе, но к тому времени Вильгельм уже почти оправился от болезни. Он грубо отказался принять гостя, а что до вопросов, которые они должны были разрешить, то пують
