Новгородцы еще раз явились с просьбами. Всеволод отвечал, чтоб они выбирали себе князя, где хотят, а из мужей отпустил только некоторых. Новгородцы «разгневались», выгнали сами Ярослава и взяли себе князем сына у князя черниговского. Изгнанный Ярослав, между тем, был принят новоторжцами, самыми близкими к мести Всеволодовой, и начал брать дань по всему верху, по Мсте за Волоком. А Всеволод употребил прежнюю меру, оказавшуюся столь действительной: велел ловить новгородцев за Волоком и на всей земле своей и привозить во Владимир, где они ходили, впрочем, на свободе.
Новгородцы опять смирились и, продержав у себя черниговского князя только полгода, вынуждены были исполнить волю Всеволодову и опять просить к себе Ярослава (1197).
Всеволод велел Ярославу прийти из Торжка к себе во Владимир, а новгородским лучшим мужам явиться за ним туда же. Так и было исполнено. Они пришли и взяли его со всей правдой и честью во Владимире, как бы из рук великого князя суздальского, в знамение его верховной власти, а их подчиненности. Всеволод отпустил тогда и всех новгородцев, томившихся у него в неволе, – посадник Мирошка, сидевший два года под стражей, также возвратился в Новгород, к общему удовольствию его сограждан.
Но через год (1199) Всеволоду вздумалось самому вывести Ярослава из Новгорода и посадить там сына. Он велел владыке Мартирию, посаднику Мирошке и лучшим мужам приехать к нему во Владимир за сыном. Разительное доказательство его власти! На озере Селигере архиепископ Мартирий скончался, тело его отвезено было в Новгород к Святой Софии, а посадник Мирошка и лучшие мужи прибыли к Всеволоду и сказали: «Ты господин князь великий Всеволод Юрьевич! Просим у тебя сына княжить Новгороду, зане отчина тебе и дедина Новгород». Всеволод принял послов с великой честью, утвердил честным крестом на всей воле своей и дал им в князья Святослава, еще четырехлетнего младенца, который и приведен был к ним 1 января 1200 года.
Согласившись с посадником, Всеволод дал новгородцам архиепископа Митрофана, который поехал в Киев на поставление в сопровождении новгородских и Всеволодовых мужей.
Наступала пора отомстить Рюрику, который взял перед тем назад города, уступленные им великому князю суздальскому.
Всеволод не спускал глаз с Юга, и в 1195 году он прислал тиуна своего Гюрю с людьми, создать «град на Городци на Востри» и обновил свою отчину. В 1197 году дал епископа Павла в Переяславль. В 1198 году, по смерти племянника Ярослава Мстиславича в Переяславле-Русском, прислал туда княжить своего сына Ярослава, еще отрока, так же как в Новгород младенца Святослава. Теперь у Рюрика с Романом началась новая распря. Всеволод принял сторону Романа, который заставил тестя отказаться от Киева и идти в свой старый Овруч. На киевском столе посажен был тогда именем Всеволодовым и Романом Ингварь Ярославич луцкий (1202). Рюрик хоть взял город (1 января 1204 г.), соединившись с половцами и Ольговичами, но не мог его удержать за собой без согласия Всеволода и удалился в свой Овруч.
Роман, желая оторвать своего тестя от половцев и Ольговичей, взявших тогда его сторону, пришел было к нему мириться во Вручий. «Слися, – сказал он, – к свату своему великому князю Всеволоду, и я слюся к нему, к своему отцу и господину, и молимся ему, чтоб он отдал тебе Киев опять». Рюрик поверил Роману и поцеловал крест Всеволоду, с сыновьями и братьями.
И Всеволод не помянул зла, достигнув своей цели, то есть получив, может быть, прежние города: он опять отдал Рюрику Киев.
Ольговичи также, при посредстве Романа, который молился за них великому князю, «дабы приял их в любовь», примирились с Всеволодом, и он прислал своего боярина Михаила Борисовича привести их к кресту. Черниговские бояре ездили к Владимиру, и великий князь целовал при них крест. Роман присягнул также. Южная Русь успокоилась хоть ненадолго; Всеволод обратился к Северной.
Он решил вывести Святослава, княжившего четыре года, из Новгорода, сказав новгородцам: «По земле вашей ходит рать, а князь ваш, сын мой, Святослав, мал: даю вам старейшего сына своего Константина» (1205).
Отпуская Константина, Всеволод сказал ему: «Сын мой Константин! Бог положил на тебе старейшинство во всей братье твоей и во всей Русской земле, а Новгород Великий имеет старейшинство между всеми княженьями в Русской земле. По имени твоем и хвала твоя. Поезжай в свой город. И я даю тебе старейшинство». Всеволод дал ему меч и крест: «Се буди тебе охранник и помощник, а меч прещенье и спасенье, пасти люди твоих от противных». С этими словами, поцеловав, отпустил его. Все братья его – Георгий, Владимир, Иоанн – бояре отца его, купцы проводили его с честью великой до реки Шедакши. «От множества людей, – говорит летопись, – великий был говор, доходящий как будто до неба: все радовались, и, настигшу вечеру, поклонились ему братья его, мужи отца его, послы от братьев, воздавая хвалу великую и простились».
Таким образом, Всеволод стал как бы полным господином Новгорода и, разумеется, делал, что хотел.