Во Владимире был расширен кремль, построены стены и более красивые и крепкие башни, чем даже в Суздале. В других городах Всеволод тоже возводил постройки, которые стали памятниками. Но главная из них – чудо времен Всеволода и одна из тех построек, которая спустя века прославляет Владимир, – это собор, который он возвел в честь мученика Дмитрия Солунского, погибшего в Салониках. Не равный по размерам и богатству убранства церкви, которую построил Андрей, собор превзошел эту постройку с золотым куполом по пропорциям и красоте. Кроме того, он был известен изящными и разнообразными внешними украшениями. Но любящий Бога строитель церкви обогатил ее реликвиями более ценными для верующих, чем серебро или золото. Этими сокровищами была икона Дмитрия Солунского, пропитанная кровью сорочка и несколько костей великомученика.
Безграничную радость испытали владимирцы, когда эти священные реликвии были привезены в город.
Рязань была источником большого беспокойства для Всеволода, так как ее князья всегда ссорились и без колебаний открыто угрожали друг другу уничтожением. Великий князь был вынужден положить конец этим ссорам. Чтобы защитить свои города, он должен был оборонять рязанские земли от половцев. Наглость этих кочевников усилилась на фоне ссор рязанских князей. Ввиду этого Всеволод выступил в поход против половцев и отправился вглубь донских земель. Он нанес удар по степному региону, который занимали «дикие» половцы, нападавшие на Рязань. Он совершил быстрый переход и напал на их зимние стойбища, но его проворные враги немедленно ускользнули; он просто напугал их. Для того чтобы защитить Рязань, необходимо было держать ее под контролем.
В этот период межфракционная борьба в Новгороде иногда угрожала миру во Владимире, но Всеволоду не было нужды поддерживать князей, которых он послал в этот город по его же просьбе. Он ничего не делал для того, чтобы помешать Новгороду сменить своего князя. Когда его горожане стали жаловаться на Ярослава, Всеволод заменил его на Мстислава – сына Давыда Смоленского – своего союзника в походе на булгар. Когда Новгород, которому никогда подолгу не нравился ни один князь, во второй раз попросил себе Ярослава, он его получил. Не единожды эти два малозначительных князя правили в Новгороде. Позднее оттуда Всеволод получил такое послание: «Новгород – наследство твоего отца и деда; пришли к нам твоего собственного сына».
Всеволод послал Святослава – одного из своих младших сыновей, который в то время был мальчиком. Несколько раз этого сына возвращали отцу, а потом опять отсылали в Новгород по его просьбе. Так как великий князь держал в своих руках контроль над дорогами в Новгород, он обеспечивал в нем мир, и этот город не беспокоил его, но дела в Рязани были запутанными и вызывали тревогу.
Старший рязанский князь Роман довел своих братьев до междоусобной войны. Он был тщеславным и честолюбивым человеком и, будучи зятем киевского князя, воображал о себе гораздо больше, чем следовало. Младшие братья Романа – Игорь и Владимир, которые вместе с ним владели Рязанью, – пригласили Всеволода и Святослава – своих братьев, правивших в Пронске, к себе погостить. Эти младшие братья узнали, что пригласившие их родственники задумали пленить или убить их, и остались в Пронске и укрепили город. Старшие братья скорым маршем выступили на Пронск, осадили город и разграбили его окрестности. Начав эту войну, Роман и его братья, видимо, тем самым осудили своих младших братьев за доброе отношение к князю Владимира и заявили, что они сами и в грош не ставят Владимирское княжество. Таким образом, их действия были вызовом Всеволоду, и он очень быстро ответил на них. Не вмешиваясь в ссору между братьями, он послал двух своих бояр в Рязань со следующим сообщением, которое на самом деле было предупреждением: «Я не удивлен, что язычники опустошают ваши земли. Но я удивляюсь тому, что вы, вместо того чтобы жить, как братья, и охранять свои земли от булгар и половцев, нападаете друг на друга и убиваете свой собственный народ. Я этого не позволю. Бог послал меня хранить справедливость и защищать людей, приводить к повиновению тех, кто преступно нарушает закон. Боюсь, если я не стану проявлять об этом заботу, Бог спросит с меня за преступления, совершаемые вами. О, братья, какой вред вы причиняете! Предоставляю вам судить об этом».