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