Всеволод немедленно приказал перехватывать всех новгородских купцов на Владимирской земле. Он остановил торговлю между этими двумя городами и начал настоящую войну. Это сильно встревожило новгородцев, и они показали Ярополку дорогу, ведущую из их города. И хотя сам Всеволод был доволен изгнанием Ярополка и готов снять блокаду, войну продолжил народ. Причиной послужило то, что владимирцы и тверичи думали, что она затрагивает не только честь их князя, но и в еще большей степени – их прибыль. Они хотели положить конец посягательствам Великого Новгорода. Они снова обвинили Всеволода в добросердечии и нерешительности. «Новгородцы, – сказали они, – каждый день дают клятвы, но постоянно нарушают их. Мы собираемся не целоваться с новгородскими воинами, а остановить их наступление». Затем они взяли Новый Торг, связали там всех мужчин, способных воевать, захватили их женщин и детей, забрали все товары, сожгли город и отправили связанных пленников во Владимир.
Тогда Всеволод отправился в Новый Торг, но, не дойдя до города, решил, что уже достаточно наказал Новгород, и возвратился во Владимир. Вскоре после этого новгородцы пригласили Мстислава Храброго – сына смоленского князя Ростислава – править в Новгороде. Мстислава Великого почитали больше всех когда-либо правивших князей, а Мстислав Храбрый был его внуком. Однако сердце молодого князя не лежало к городу, и чем больше он думал об этом приглашении, тем больше склонялся к отказу. Но его братья и дружина стали убеждать его, и в конце концов он уступил их уговорам и поехал в Новгород, где был встречен торжественной процессией со всеми почестями. Он посетил Святую Софию, после чего сел на трон своих отца и деда.
Больше всего новгородцы ценили службу, которую служили им их князья, по защите их города от язычников – чуди, которые налетали со стороны Балтики. Границы псковских и новгородских земель сильно страдали сначала от диких людей из неизвестных бескрайних земель. В конечном счете они были разгромлены и обложены данью, составной частью которой была переправа товаров и кораблей волоком. Перед приходом Мстислава к власти эти люди, отправленные для переноски товаров, вдруг стали грабителями. Когда князь получил власть, он созвал лучших новгородских людей и сказал: «Братья, давайте освободим Новгородскую землю от обидчиков». Все ответили как один: «Если этого желает Бог и ты, мы готовы».
Когда войска собрались и Мстислав выстроил их на смотр, он обнаружил, что их численность составляет двадцать тысяч человек. Он отправился в земли язычников, и эти двадцать тысяч воинов отправились вместе с ним. Он прошел эти земли из конца в конец, не останавливаясь, пока не достиг морского побережья. Он захватил людей, скот и имущество; когда была необходимость наказывать, он превращал все на своем пути в пепел. Одним словом, он приводил всех к повиновению. Затем он повернул к Пскову.
Согласно принятому издревле обычаю, псковский посадник назначался Новгородом, но на тот момент шли бесконечные споры между двумя городами. Псковичи хотели независимости и своего собственного князя. На протяжении зимы 1180 г. Мстислав планировал на весну военный поход. Он помнил обиды, нанесенные полоцким князем Всеславом Чародеем, который, как говорили люди, мог оборачиваться серым волком и за одну ночь пробежать от Кавказа до Новгорода. Когда-то Всеслав захватил часть Великого Новгорода, увез его вечевой колокол, святые образа и церковную утварь. Мстислав решил все это возвратить в город. Князем Полоцка в то время был Всеслав – зять Романа Ростиславича.
Когда пришла весна, Мстислав выступил на Полоцк вместе со своим войском. Роман послал своего представителя ему навстречу с такими словами: «Всеслав не нанес тебе никакой обиды, почему же ты идешь на него войной? Если ты решишь напасть, ты встретишь меня впереди всех». Не желая обижать своего старшего брата, Мстислав отказался от своего предприятия. Едва он достиг Великого Новгорода, как захворал. Никто не мог понять, что с ним такое. Некоторое время он лежал в беспамятстве. Его жена стояла у его постели вместе с его дружинниками и лучшими друзьями. Когда сознание к нему вернулось, он посмотрел на присутствовавших, и слезы навернулись ему на глаза. Лишь немногие произнесенные им слова имели смысл. Своего младшего сына Владимира он поручил заботам своего любимого боярина. Из двух сыновей, оставленных им двум его братьям, один стал широко известен в более поздние годы как Мстислав Удалой. «Не забудьте о моих сыновьях», – просил он своих братьев. Он поднял руки, глубоко вздохнул, слезы снова выступили у него на глазах, и дыхание остановилось.