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

Чтимый внутри и вне России, Всеволод хотел искреннего взаимного дружелюбия Князей и старался утвердить оное новым свойством, выдав дочь свою за племянника Святославова, — другую, именем Верхуславу, за Рюриковича, мужественного Ростислава, а сына своего Константина, еще десятилетнего, женив на внуке умершего Романа Смоленского.