Владимир Галицкий, заключенный с женою и с детьми у Короля Венгерского, нашел способ уйти: изрезал шатер, поставленный для него в башне, свил из холста веревки, спустился по оным вниз и бежал к Немецкому Императору, Фридерику Барбаруссе. Так сын Ярослава Великого искал некогда покровительства Императора Генрика IV; но привез сокровища в Германию, а Владимир мог только обещать и действительно вызвался ежегодно платить Фридерику 2000 гривен серебра, буде его содействием отнимет Галич у Венгров. Император — неизвестно, каким образом — знал Великого Князя Суздальского и весьма ласково принял Владимира, слыша, что он сын Всеволодовой сестры. Хотя, занятый тогда важным намерением ратоборствовать в Палестине с Героем Востока, Саладином, Фридерик не мог послать войска к берегам Днестра, однако ж дал Владимиру письмо к Казимиру Справедливому, которое имело счастливое для изгнанника действие: ибо сей Монарх Польский, завидуя Венграм в приобретении земли Галицкой и ведая, сколь их господство противно ее жителям, не отказался от предлагаемой ему чести быть покровителем несчастного Князя, вероломно обманутого Белою; надеялся на Галичан и не обманулся. Быв недовольны правлением Владимировым, они еще гораздо более ненавидели Венгров; и когда услышали, что сей Князь с Воеводою Краковским, знаменитым Николаем, идет к их границам: то все единодушно восстали, изгнали Андрея и встретили Владимира с радостию; а Беле остался стыд и титул Короля Галицкого , с 1190 года употребляемый в его грамотах. Еще не миновались опасности для Владимира: худо веря бескорыстию Поляков, боясь Венгров, Романа Волынского и собственного народа, он прибегнул к дяде, Великому Князю, не хотев дотоле искать в нем милости; смиренно винился, обещал исправиться и писал к нему: «Будь моим отцом и Государем: я Божий и твой со всем Галичем; желаю тебе повиноваться, но только тебе одному». Сие покровительство, согласное с долгом родства, было лестно и для гордости Всеволода, который, взяв оное на себя, известил о том всех Князей Российских и Казимира: после чего Владимир мог безопасно господствовать до самой смерти.

Чтимый внутри и вне России, Всеволод хотел искреннего взаимного дружелюбия Князей и старался утвердить оное новым свойством, выдав дочь свою за племянника Святославова, — другую, именем Верхуславу, за Рюриковича, мужественного Ростислава, а сына своего Константина, еще десятилетнего, женив на внуке умершего Романа Смоленского. Юность лет не препятствовала брачным союзам, коих требовала польза государственная. Верхуслава также едва вступила в возраст отроковицы, когда родители послали ее к жениху в Белгород. Сия свадьба была одною из Великолепнейших, о коих упоминается в наших древних летописях. За невестою приезжали в Владимир шурин Рюриков, Глеб Туровский, и знатнейшие Бояре с супругами, щедро одаренные Всеволодом. Отменно любя Верхуславу, отец и мать дали ей множество золота и серебра; сами проводили милую, осьмилетнюю дочь до третьего стана и со слезами поручили сыну Всеволодовой сестры, который должен был, вместе с первыми Боярами Суздальскими, везти невесту. В Белогороде Епископ Максим совершал обряд венчания, и более двадцати Князей пировали на свадьбе. Рюрик, следуя древнему обычаю, в знак любви отдал снохе город Брагин. Сей Князь, тесть Игорева сына, жил в мире со всеми Ольговичами и в случае споров о границах или Уделах прибегал к посредству Всеволодову. Так, Святослав (в 1190 году) желал присвоить себе часть Смоленских владений; но Рюрик и Давид вместе с Великим Князем обезоружили его, представляя, что он взял Киев с условием не требовать ничего более и забыть споры, бывшие при Великом Князе Ростиславе; что ему остается или исполнить договор, или начать войну.