Эго обстоятельство порождало порой ожесточённую борьбу за место новгородского князя между ведущими княжествами Руси, особенно между Киевом и Владимиро-Суздальской землёй. Вели эту борьбу Юрий Долгорукий, потом Андрей Боголюбский; продолжил её и Всеволод.
В 1179 году новгородцы пригласили на княжение Мстислава Храброго, известного своими военными походами и многими битвами, в которых он участвовал. Слава его гремела по всей Руси. Пишет летопись, что от юности своей Мстислав Ростиславич не привык бояться никого, кроме единого Бога, поступал вопреки чужому мнению и грубой силе, показывал храбрость и в бою, и в обыденной жизни. Известно, что когда всесильный Андрей Боголюбский прислал в Киев своего боярина Михну с заданием посадить на престол нужного человека, Мстислав единственный не устрашился его, приказал отрезать бороду и волосы на голове Михны и с позором отправить обратно во Владимир, а затем организовал оборону Вышгорода от владимирских войск и добился победы.
Теперь этот князь заявился в Новгород. Жители с восторгом встречали знаменитого человека, людское море окружило его со всех сторон. А он ехал на белом коне, в роскошной княжеской одежде, красивый лицом и сильный телом и доброжелательно улыбался и кивал восхищенной толпе.
Поднявшись на помост, он сразу задал вопрос:
— А куда бы нам, господа новгородцы, пойти воевать?
Тут же к нему выскочило несколько человек и стали рассказывать, как в 1176 году на Псковскую землю пришла чудь и стала грабить селения. Псковичи при поддержке новгородцев вступили с ними в лютую битву, много народу" полегло в ней. Сумели отогнать супостата, но боль и обида осталась и требовала отмщения.
— Пойдём на чудь! — весело сказал Мстислав Храбрый. — Записывайтесь в моё ополчение!
Охотников идти в поход с таким боевым князем оказалось много, более 20 000 человек. С сильными полками он вторгся в Чудскую землю, пожёг её и возвратился домой с победою, славою и честию великой.
Зиму провёл в Новгороде, а весной вновь стал думать с дружиной: куда бы ещё пойти воевать? И придумал двинуться на зятя своего, полоцкого князя Всеслава. Когда-то, лет сто назад, один из полоцких князей ходил на Новгород, взял много добычи, увёз утварь церковную и людей новгородских поселил на своей земле, заставив работать на себя. Вспомнили эту обиду дружинники, убедили князя пойти отомстить соседу.
Уже двинулась новгородская дружина в поход, как из Смоленска явился к нему посол от брата — Романа Ростиславича с посланием: «Всеслав тебя ничем не обижал, а если идёшь на него так, без причины, то прежде ступай на меня». Верный во всём старине, Мстислав не смел ослушаться старшего брата, тем более что он уже отправил на помощь Всеславу сына своего, и новгородцам пришлось бы сражаться не только с полочанами, но и со смолянами, и повернул назад. В пути он захворал, потерял силы, едва мог говорить и по возвращении в Новгород умер. Плакала по Мстиславу Храброму вся земля Новгородская; сильно горевали братья, услыхавши о его смерти, плакала по нём вся земля Русская, которая не могла забыть доблестей его, как придавал он своими словами храбрость дружине своей и от всего сердца бился за отчизну свою.
Осторожный и расчётливый, Всеволод на первых порах не вмешивался в новгородские дела. Но после смерти Мстислава Храброго явился со своим войском под Торжок, осадил его и принудил новгородцев принять князем его сына Ярослава, а потом железной рукой держал в повиновении феодальную республику. Бунтовали новгородцы, прогоняли и Ярослава, и других его сыновей, но Всеволод или направлял свои полки под Торжок и другие города, или перекрывал потоки хлеба из Владимиро-Суздальской земли, и тогда жители вольного города начинали испытывать голод и вынуждены были идти на уступки великому князю.
Недовольные владимирским правлением, купцы и бояре в 1203 году послали приглашение занять княжеский пост сыну Мстислава Храброго — Мстиславу Торопецкому. Тот немедленно явился, пришёл на вече, высокий, статный, красивый, весь в отца. Площадь встретила его с ликованием.
— Помните моего батюшку? — вопрошал Мстислав.
— Зна-а-ам! — дружно ответила толпа.
— Вот я так же, как и отец, буду твёрдо стоять на защите ваших вольностей. Люб я вам?
— Лю-ю-бо-о-о! — одним дыханием произнесла толпа.
— Тогда пойдёмте и изгоним из города владимирского князя Святослава! — призвал он.
Святослава Всеволодовича с дружиной заперли в архиепископом доме. В ответ Всеволод захватил купцов новгородских и с полками двинулся к Торжку. Два князя встали друг перед другом. Всеволод всегда старался избегать кровопролития, поэтому послал гонца сказать Мстиславу:
— Ты мне сын, а я тебе отец, отпусти Святослава с дружиною и отдай всё, что захватил, а я так же отпущу гостей (купцов) и товары их.
Мстислав согласился, мир был заключён. Но Новгород для Всеволода был потерян.
Владимиро-Суздальская земля через Волгу вела оживлённую торговлю с прикаспийскими странами, персами, арабами, турками. Но на пути лежало Булгарское царство, правители его чинили помехи русским купцам. Те приходили к великому князю, жаловались. По их настоянию Всеволод трижды — в 1184,1186 и 1205 годах — успешно ходил на Булгарию и добился значительных льгот для русских торговцев.
В 1194 году вспыхнула острая междоусобная война сразу между несколькими князьями Южной Руси. Сначала не поладили друг с другом князь смоленский Давыд и черниговские князья Ярослав и Игорь. Тотчас к Давыду присоединился его брат, князь белгородский Рюрик Ростиславич, а на сторону черниговских князей выступили полоцкий князь Всеслав Васильич с ливами, литвою и половцами. Противники встретились на реке Судость, выбрали выгодное положение и целую неделю перестреливались, не спеша вступать в решающую битву.
На левом крыле черниговцев располагались половцы. Их пришло много, они лежали на лугу безо всякой осторожности, надеясь на силу русских полков. Увидев это, чёрные клобуки — торки и берендеи, — не слушаясь приказов русских воевод, бросились на половцев, врезались в их стан, но были отброшены назад и в бегстве смяли дружину князя Давыда, которая также обратилась в бегство, а за нею и сам князь. Но остались на своих местах закалённые в боях воеводы Лазарь, Борис Захарыч и Сдеслав Жирославич. Их не смутило бегство чёрных клобуков и смолян; выждав удобный момент, они ударили в бок расстроенному войску черниговцев и половцев, смяли их и погнали; много неприятельских воинов погибло в реке, другие были перебиты или захвачены в плен. Слава этой победы пала на князя Рюрика, который хотя и был в стороне, но не дрогнул и остался под княжеским стягом; ко всему прочему он оказался единственным князем, не покинувшим поле боя. Победители вошли в Стародуб и по обычаю устроили пир.
В самый разгар пиршества в Стародуб заехал князь владимирский Всеволод со своими детьми. Он гостил у Святослава, князя киевского, и возвращался к себе домой. Всеволода тотчас пригласили к столу, усадили в красный угол, стали угощать. Тут же воеводы наперебой начали рассказывать ему, как под руководством князя Рюрика было разбито многочисленное войско черниговцев и полочан, а также орда половцев и ватаги ливов и литвы.
— Противник уже смял мои полки, мы уже спасались бегством, — захлёбываясь, поддакивал им князь Давыд. — Но тут откуда ни возьмись вихрем налетел на противника князь Рюрик и сбросил его в реку!
Тут бы Рюрику следовало вмешаться и поправить и князя, и воевод, но тщеславие взяло верх; он только победоносно поглядывал на всех и охотно принимал незаслуженные похвалы.
— Молодец, молодец, — проговорил Всеволод, любовно глядя на Рюрика. — Настоящий князь! Такого и в Киеве не грех посадить!
— А как Святослав Всеволодович, поправился от болезни? — спросил воевода Борис Захарыч. Все знали, что князь последние месяцы недомогал, отошёл от государственных дел и большую часть времени проводил не в Киеве, а в Вышгороде.
— Пока я гостил у него, вроде бы пошёл на поправку и даже повеселел, хотя выглядит неважно, — ответил Всеволод.
— Случись что, снова начнётся передел власти в Южной Руси, снова вернётся смута, — задумчиво проговорил воевода Лазарь.
— Не будет смуты, коли князь наш, Всеволод Юрьевич, по праву и силе своей займёт киевский престол! — рубанув крепкой ладонью по столу, сказал Борис Захарыч.
— Некрасивый разговор мы завели, — урезонил собеседников Всеволод. — Святославу Всеволодовичу жить да жить, а вы его власть уже начали делить.
— Не делим мы, не по чину нам такое, — возразил Сдеслав Жирославич. — Но мнение своё высказать можем. Разорена Южная Русь и княжеской смутой, и половецкими набегами. Вся сила Руси сегодня на наш суздальский север переместилась, чуть ли не половина населения к нам перешла. Так кому владеть державой, как не князю Суздальскому?
