Так же грозен был Всеволод и другим соседним князьям смоленским: под 1206 годом находим в летописи известие, что смоленский епископ Михаил вместе с игуменом Отроча монастыря приезжали во Владимир упрашивать Всеволода, чтоб простил их князя Мстислава Романовича за союз с Ольговичами. Новгороду Великому при Всеволоде также начинала было грозить перемена в его старом быте. Мы оставили Новгород в то время, когда вопреки воле Боголюбского и Ростиславичей жители его приняли к себе в князья сына Мстислава Изяславича, знаменитого Романа, вследствие чего должны были готовиться к опасной борьбе с могущественным князем суздальским. В 1169 году Данислав Лазутинич, тот самый, которй успел провести Романа в Новгород, отправился на Северную Двину за данью с 400 человек дружины; Андрей послал семитысячный отряд войска перехватить его, но Данислав обратил в бегство суздальцев, убивши у них 1300 человек, а своих потерявши только 15. После этого Лазутинич отступил, как видно, боясь идти дальше, но потом спустя несколько времени двинулся опять вперед и благополучно взял всю дань, да еще на суздальских подданных другую. Андрей, однако, недолго сносил торжество новгородцев; выгнавши отца из Киева, он послал сильную рать выгонять сына из Новгорода: это было зимою 1169 года; войско повели сын Андреев, Мстислав, да воевода Борис Жирославич, была тут вся дружина и все полки ростовские и суздальские, к ним присоединились князья смоленские - Роман и Мстислав Ростиславичи, потом князья рязанские и муромские, войску, по свидетельству летописца, и числа не было. После страшного опустошения Новгородской волости оно подошло к городу, но жители его затворились с своим молодым князем Романом, с посадником Якуном и бились крепко; четыре приступа не удались; в последний из них, продолжавшийся целый день, князь Мстислав въехал было уже в ворота городские и убил несколько человек, но был принужден возвратиться к своим. Новгородцы и Роман торжествовали победу, а между тем в полках у осаждающих обнаружился мор на людях и конский падеж. Рать Андреева должна была отступить, ничего не сделавши, и отступление это было гибельно по опустошенной стране: одни померли в дороге, другие кое-как дошли пешком до домов, много попалось в плен к новгородцам, которые продавали по две ногаты человека. Но опустошение, причиненное Андреевою ратью, имело тяжкие следствия и для Новгорода: в нем сделался сильный голод, а хлеба можно было только достать с востока, из областей Андреевых; притом же Мстислав Изяславич умер, не было больше основания держать его сына, и вот новгородцы показали путь Роману, а сами послали к Андрею за миром и за князем. К ним явился княжить Рюрик Ростиславич; неизвестно, каким образом Якун лишился посадничества: по всем вероятностям, мир с Андреем и Ростиславичами условливал смену посадника, так сильно поддерживавшего в новгородцах сопротивление суздальскому князю. Преемником Якуна является Жирослав, но Рюрик отнял посадничество и у этого и дал его Ивану Захарьичу, сыну прежнего посадника Захарии, который был убит народом за приверженность к брату Рюрикову, Святославу; Рюрик не только отнял посадничество у Жирослава, но даже выгнал его из города, и тот ушел к Андрею в Суздаль. Но в тот же год сам Рюрик ушел из Новгорода: брат его Роман, севши в Киеве, дал ему волость на Руси, и новгородцы отправили к Андрею послов просить другого князя; Андрей пока отпустил к ним Жирослава посадничать с своими боярами, а потом в следующем году прислал сына Юрия, но Жирославом, как видно, были недовольны в Новгороде, и архиепископ Илья отправился во Владимир к Андрею, чтоб уладить окончательно все дела; следствием поездки было то, что посадничество опять отдали Ивану Захарьевичу.
Смерть Боголюбского повела снова к переменам в Новгороде: сын его Юрий должен был уступить место сыну Мстислава Ростиславича, призванного ростовцами, но в тот же год сам Мстислав, разбитый дядею Михаилом и выгнанный из Ростова, сменил сына в Новгороде. В том же 1175 году умер посадник Иван Захарьевич, посадничество получил опять было Жирослав, но в конце года лишился его снова, и место его заступил Завид Неревинич, сын того боярина Неревина, который был убит вместе с Захариею. Только что успел Мстислав Ростиславич жениться в Новгороде на дочери старого Якуна Мирославича, как был позван опять ростовцами, опять был побежден, выгнан дядею Всеволодом и пришел назад в Новгород, но здесь показали ему путь вместе с сыном, которого, как видно, он вторично оставил вместо себя, и взяли князя из рук победителя Всеволода, который прислал в Новгород племянника своего Ярослава Мстиславича. Но Ростиславич, по всем вероятностям, оставил по себе в Новгороде сильную сторону, в челе которой, разумеется, должен был стоять тесть его Якун; в следующем же 1177 году он явился в Новгороде, был посажен на стол, брату его Ярополку дали Торжок, а Ярославу, прежнему князю, - Волок-Ламский - знак, что он отступил от Всеволода к врагам его, Ростиславичам. Легко понять, что Всеволод не мог спокойно видеть последних князьями в соседних волостях новгородских, притом же не мог он простить новгородцам нарушение обещания признавать его верховную власть и другого обещания придти к нему на помощь в войне с Глебом рязанским; в 1178 году, когда Мстислав Ростиславич умер и новгородцы посадили себе князем брата его, Ярополка, Всеволод велел захватить по своей волости купцов новгородских; новгородцы испугались и выгнали Ярополка, но князю новых городов мало было одной чести давать из своих рук князей старому городу: он хотел какой-нибудь более существенной пользы и выступил в поход к Торжку, жители которого обещали давать ему дань; подойдя к городу, Всеволод сначала не хотел было брать его приступом, дожидаясь исполнения обещаний, но дружина стала жаловаться и побуждать его к приступу, говоря: «Мы не целоваться с ними приехали; они, князь, богу лгут и тебе». Войско бросилось к городу и взяло его, жителей перевязали, город сожгли - за новгородскую неправду, прибавляет летописец, потому что новгородцы на одном дне целуют крест и нарушают свою клятву. Отправив пленных новоторжан во Владимир, Всеволод пошел к Волоку-Ламскому; жители его успели выбежать, но князь их Ярослав Мстиславич был схвачен и город сожжен. Новгородцы между тем послали за ближайшим к себе князем Романом Ростиславичем смоленским, который и приехал к ним, а Всеволод, до вольный большою добычею и не желая, как видно, иметь дела с Ростиславичами южными, возвратился во Владимир.
Роман недолго пожил в Новгороде: в следующем же 1179 году он уехал назад в Смоленск, и новгородцы послали звать на княжение брата его, Мстислава Ростиславича, знаменитого своею борьбою с Боголюбским. Здесь начинается союз Новгорода с двумя Мстиславами - отцом и сыном - самыми блестящими представителями старой, Юго-Западной, Руси в борьбе ее с новою, Северо-Восточною. Союз этот был необходим по одинаковости стремлений: как Новгород, так и Мстиславы хотели поддержать старый порядок вещей против нового, поддержать родовые отношения между князьями и вместе старый быт старых городов. Сперва Мстислав не хотел было идти в Новгород по общей князьям того племени привязанности к югу, к собственной Руси и по опасности, которая грозила там Мономаховичам от Ольговичей: «Не могу выйти из своей отчины и разойтись с братьями», - говорил Мстислав. Он всеми силами старался, говорит летописец, трудиться для отчины своей, всегда стремился он к великим делам, думая думу с мужами своими, желая быть верен своему происхождению, своему значению княжескому (хотя исполнити отечествие свое). Но братья и дружина уговаривали его идти в Новгород, они говорили ему: «Если зовут тебя с честию, то ступай, разве там не наша же отчина?» Мстислав пошел, но положил на уме: «Если бог даст мне здоровья, то никак не могу забыть Русской земли». Каков был характер этого Мстислава, представителя наших старых князей, как понимал он обязанности своего звания, исполнение отечествия своего, видно из того, что едва успел он придти в Новгород, как начал думать, куда бы пойти повоевать? Незадолго перед тем, в 1176 году, чудь приходила на Псковскую землю, имела злую битву с псковичами, в которой с обеих сторон легло много народу. И вот Мстислав вздумал пойти на чудь; он созвал новгородцев и сказал им: «Братья! Поганые нас обижают; чтобы нам, призвавши на помощь бога и святую богородицу, отомстить за себя и освободить землю Новгородскую от поганых?» Люба была его речь всем новгородцам, и они отвечали ему: «Князь! Если это богу любо и тебе, то мы готовы». Мстислав собрал новгородское войско и, сочтя его, нашел 20000 человек; с такими-то сильными полками вошел он в Чудскую землю, пожег ее всю, набрал в плен челяди и скота и возвратился домой с победою, славою и честью великою. по словам летописца. Возвращаясь из Чудской земли, по дороге заехал Мстислав во Псков, перехватил там сотских, которые не хотели иметь князем племянника его, Бориса Романовича, и, утвердившись с людьми, пошел в Новгород, где и провел зиму.