Сын Князя Иоанна Берладника, умершего в Фессалонике, двоюродный племянник Ярослава Галицкого, именем Ростислав, подобно отцу скитался из земли в землю и нашел пристанище в Смоленске. Он имел друзей в отечестве, где народ, неохотно повинуясь иноземным властителям, и некоторые Бояре желали видеть его на престоле. По согласию с ними Ростислав, уехав от Давида Смоленского, с малым числом воинов явился пред стенами Галича, в надежде, что все граждане к нему присоединятся. Но Андрей оградил себя полками Венгерскими, взял с жителей, волею и неволею, присягу в верности и вообще такие меры, что сын Берладников вместо друзей встретил там одних врагов многочисленных. Видя неудачу, измену или робость Галичан, Ростислав не думал спасаться бегством; сказал дружине: "Лучше умереть в своем отечестве, нежели скитаться по чужим землям; предаю суду Божию тех, которые меня обманули" - и бросился в средину неприятелей. Тяжело раненный, он упал с коня и был привезен в столицу, где народ, тронутый его жалостною судьбою, хотел возвратить ему свободу. Чтобы утишить мятеж, Венгры, как сказано в летописи, приложили смертное зелие к язве Ростислава, и сей несчастный Князь, достойный лучшей доли, скончался, имев только время удостовериться в народной к нему любви; а граждане, изъявив оную, раздражили своего Короля. Правление Андреево, дотоле благоразумное, снисходительное, обратилось в насилие. Венгры мстили Галичанам как изменникам, нагло и неистово: отнимали жен у супругов, ставили коней в домы Боярские, в самые церкви; позволяли себе всякого рода злодейства. Народ вопил, с нетерпением ожидая случая избавиться от ига: он представился.
Владимир Галицкий, заключенный с женою и с детьми у Короля Венгерского, нашел способ уйти: изрезал шатер, поставленный для него в башне, свил из холста веревки, спустился по оным вниз и бежал к Немецкому Императору, Фридерику Барбаруссе. Так сын Ярослава Великого искал некогда покровительства Императора Генрика IV; но привез сокровища в Германию, а Владимир мог только обещать и действительно вызвался ежегодно платить Фридерику 2000 гривен серебра, буде его содействием отнимет Галич у Венгров. Император - неизвестно, каким образом - знал Великого Князя Суздальского и весьма ласково принял Владимира, слыша, что он сын Всеволодовой сестры. Хотя, занятый тогда важным намерением ратоборствовать в Палестине с Героем Востока, Саладином, Фридерик не мог послать войска к берегам Днестра, однако ж дал Владимиру письмо к Казимиру Справедливому, которое имело счастливое для изгнанника действие: ибо сей Монарх Польский, завидуя Венграм в приобретении земли Галицкой и ведая, сколь их господство противно ее жителям, не отказался от предлагаемой ему чести быть покровителем несчастного Князя, вероломно обманутого Белою; надеялся на Галичан и не обманулся. Быв недовольны правлением Владимировым, они еще гораздо более ненавидели Венгров; и когда услышали, что сей Князь с Воеводою Краковским, знаменитым Николаем, идет к их границам: то все единодушно восстали, изгнали Андрея и встретили Владимира с радостию; а Беле остался стыд и титул Короля Галицкого, с 1190 года употребляемый в его грамотах. Еще не миновались опасности для Владимира: худо веря бескорыстию Поляков, боясь Венгров, Романа Волынского и собственного народа, он прибегнул к дяде, Великому Князю, не хотев дотоле искать в нем милости; смиренно винился, обещал исправиться и писал к нему: "Будь моим отцом и Государем: я Божий и твой со всем Галичем; желаю тебе повиноваться, но только тебе одному". Сие покровительство, согласное с долгом родства, было лестно и для гордости Всеволода, который, взяв оное на себя, известил о том всех Князей Российских и Казимира: после чего Владимир мог безопасно господствовать до самой смерти.
Чтимый внутри и вне России, Всеволод хотел искреннего взаимного дружелюбия Князей и старался утвердить оное новым свойством, выдав дочь свою за племянника Святославова, - другую, именем Верхуславу, за Рюриковича, мужественного Ростислава, а сына своего Константина, еще десятилетнего, женив на внуке умершего Романа Смоленского. Юность лет не препятствовала брачным союзам, коих требовала польза государственная. Верхуслава также едва вступила в возраст отроковицы, когда родители послали ее к жениху в Белгород. Сия свадьба была одною из Великолепнейших, о коих упоминается в наших древних летописях. За невестою приезжали в Владимир шурин Рюриков, Глеб Туровский, и знатнейшие Бояре с супругами, щедро одаренные Всеволодом. Отменно любя Верхуславу, отец и мать дали ей множество золота и серебра; сами проводили милую, осьмилетнюю дочь до третьего стана и со слезами поручили сыну Всеволодовой сестры, который должен был, вместе с первыми Боярами Суздальскими, везти невесту. В Белогороде Епископ Максим совершал обряд венчания, и более двадцати Князей пировали на свадьбе.
Рюрик, следуя древнему обычаю, в знак любви отдал снохе город Брагин. Сей Князь, тесть Игорева сына, жил в мире со всеми Ольговичами и в случае споров о границах или Уделах прибегал к посредству Всеволодову. Так, Святослав (в 1190 году) желал присвоить себе часть Смоленских владений; но Рюрик и Давид вместе с Великим Князем обезоружили его, представляя, что он взял Киев с условием не требовать ничего более и забыть споры, бывшие при Великом Князе Ростиславе; что ему остается или исполнить договор, или начать войну. Святослав дал им слово впредь не нарушать мира и сдержал оное, довольный честию первенства между Князьями южной России. Уступив Чернигов брату, Ярославу Всеволодовичу, а Рюрику знатную часть Киевской области, не имея ни Переяславля, ни Волыни, он не мог равняться силою с древними Великими Князьями, но подобно им именовался Великим и восстановил независимость Киева. Всеволод Георгиевич уважал в Святославе опытного старца (власы седые были тогда правом на почтение людей); предвидя его близкую кончину, удерживал до времени свое властолюбие и терпел некоторую зависимость могущественной области Суздальской от Киева по делам церковным.
Вместе с народом или знаменитыми гражданами избирая Епископов для Ростова, Суздаля, Владимира, но посылая их ставиться к Митрополиту Никифору, преемнику Константинову, он всегда отправлял Послов и к Святославу, требуя на то его Княжеского соизволения: ибо власть Духовная была тесно связана с гражданскою, и Митрополит действовал согласно с желанием Государя. Никифор хотел нарушить сей устав в России, самовластно посвятив в Епископы Суздалю одного Грека; но Всеволод не принял его, и Митрополит поставил иного, назначенного Великим Князем и одобренного Святославом. - Между тем, желая приближиться к древней столице, Всеволод возобновил город Остер, разрушенный Изяславом Мстиславичем: Тиун Суздальский приехал туда властвовать именем Князя. Южный Переяславль также зависел от Всеволода, который отдал его, по смерти Владимира Глебовича, другому племяннику, Ярославу Мстиславичу. Вся Украина, по словам Летописца, оплакала сего мужественного Владимира, ужасного для Половцев, доброго, бескорыстного, любившего дружину и любимого ею.