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