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