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