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