Это расстроило отношения Рюрика с Романом, который примкнул к черниговским князьям. Между тем узнав позднее (всё в том же 1196 г.), что Всеволод Юрьевич заключил мир с Ольговичами без его ведома, правитель Киева вернул себе эти города. Борьба за киевский стол вновь обострилась в 1202–1205 гг., когда против Рюрика, заключившего союз с черниговскими Ольговичами, выступил Владимиро-Волынский и Галицкий князь Роман Мстиславич. Всеволод Юрьевич склонялся к союзу с ним, но, как и в 1190 гг., старался открыто не втягиваться в усобицу и сохранять роль арбитра. В 1205 г., после гибели Романа, борьбу за Киев и Галич повели Рюрик и сын Святослава Всеволодовича Черниговский князь Всеволод Чермный. В этой ситуации, потерпев неудачу в борьбе с Ольговичами за Галич, сын Всеволода Юрьевича Ярослав под угрозой военной силы был вынужден оставить княжение в Переяславле Русском и вернуться к отцу. В 1207 г., пытаясь помочь Рюрику, Всеволод Юрьевич при поддержке новгородцев и муромских князей совершил поход на Рязанскую землю. Большинство рязанских правителей, несмотря на клятву верности, данную Владимирскому князю, склонялись к союзу с Черниговом. В результате вместо похода против Ольговичей Всеволод Юрьевич должен был арестовать рязанских князей и брать в осаду их города. Взятия Рязани удалось избежать благодаря посредничеству местного епископа Арсения (он был вынужден согласиться на выдачу во Владимир семей рязанских князей). Однако уже в 1208 г., раскрыв заговор рязанцев, Всеволод Юрьевич вывел своего сына Ярослава с княжения в Рязани (Ярослав княжил в Рязани с 1207 г.), а её архиерея, как и раньше князей, подверг заключению. Город и его пригороды были разорены и сожжены, а их жители выведены во Владимирское княжество. В 1210 г. при участии митрополита Матфея, приезжавшего из Киева во Владимир к Всеволоду Юрьевичу, произошло его примирение с Ольговичами: Всеволод Святославич Чермный сел в Киеве, а Рюрик Ростиславич получил Чернигов. Жёны рязанских князей были освобождены из плена (но князья и другие рязанцы оставались в тюрьме до смерти Всеволода Юрьевича). В 1211 г. новый союз был скреплён браком сына Всеволода Юрьевича князя Георгия (Юрия) Всеволодовича и дочери Киевского князя княгини Агафии Всеволодовны. В 1199 г. Всеволод Юрьевич и его старший сын Константин предприняли поход на Дон против половцев, но кочевники уклонились от битвы. Начиная с 1200 г. Владимирский князь стремился держать на новгородском столе кого-либо из своих сыновей: в 1200–1205 и 1208–1210 гг. это был князь Святослав (Гавриил) Всеволодович, в 1205–1208 гг. – Константин. Однако в 1210 г. новгородский стол сумел занять князь Мстислав (Феодор) Мстиславич, представитель младшей ветви правителей Смоленска. На юге Руси Всеволод Юрьевич держал под контролем такое важное владение потомков князя Юрия Долгорукого, как Переяславль Русский, в 1198 г. на Переяславскую кафедру был поставлен по настоянию Всеволода Юрьевича епископ Павел, в 1200 г. в Переяславле на княжении появился сын Владимирского князя князь Ярослав (Феодор) Всеволодович, который сменил умершего племянника Всеволода Юрьевича князя Ярослава Мстиславича (ум. в 1198 г.). В 1206 г. в Переяславле правил другой сын Всеволода Юрьевича – Владимир.