Прежде всего он отомстил боярам Кучковичам за убийство брата Андрея, убийство жестокое и, казалось бы, бессмысленное. Он им придумал лютую казнь: все участники заговора вместе с вдовой княгиней Улитой были зашиты в ивовые коробья и утоплены в озере с затхлой водой. Летописец поведал: «…и быша яко гной земны тако си окоянные Кучковичи, и погибе память их с шумом».
Всеволод Юрьевич дознался больше: Кучковичи были выходцами из ростовских земель, их вотчина находилась в сельце. Андреевском, откуда брат и взял себе жену Улиту; они были связаны с ростовскими боярами, которые давно хотели восстановить свое былое величие. Как же, издревле была Ростово-Суздальская Русь, как так случилось, что появилась Владимиро-Суздальская? Суздаль и тут на втором месте, ладно, но почему вместо Ростова стал самозванный Владимир? Убив владимирского князя, ростовские бояре готовились призвать послушного себе и снова сделать свой город стольным. И тогда потечет полагающаяся с удельных княжеств дань, обогатится город, расцветут торговля и ремесла.
Ростовские бояре так и сделали. Уж коли не вышло с Ярополком, повернули на другого. Еще не утвердившийся прочно молодой Всеволод узнал, что они призвали из Новгорода князя Мстислава Ростиславовича и тот идет на Владимир в великой силе, намереваясь лишить его княжения. Всеволод собрал рать и вышел навстречу. «Всеволод же поиде противу Мстиславу. И много послаще к нему о миру, — сообщал летописец, сочувствуя молодому князю. — Он же [Мстислав] не хоте мира, слушающе ростовцев, и бишася у Липиц, у Юрьева на поле».
Так впервые недоброй памяти междоусобица помянула реку Липицу.
Ратное счастье в битве осталось за Всеволодовой дружиной: Мстислав бежал, а «ростовцев всех повязаша».
Ратники еще не возвратились к домам — новое известие: рязанский князь Глеб сжег Москву и теперь подступал к Владимиру; в союзники взял половцев; безжалостно грабят, жгут, уводят людей в полон.
Воины Всеволода Юрьевича обрушились на насильников. Отогнали! Был схвачен главный виновник разбоя рязанский князь Глеб. Простые владимирцы вытащили его из княжеского острога-поруба, куда он был посажен, и в ярости своей ослепили.
Вороньем слетались враги с разных сторон. Возмущало русских людей — ремесленников и землепашцев, — что князья в свои разорительные походы зовут еще и иноземцев, которые толпами гонят пленных русичей в чужие страны.
Снова лавина половцев. Только идут на сей раз с князьями киевским, черниговским, новгородцами. С берегов Камы и Волги делают опустошительные набеги булгары. Молодой князь Всеволод с дружиной и пешцами из простых людей мужественно обороняет землю.
Постепенно его начинают побаиваться— силу набрал: в относительной независимости от стольного Владимира только далекая южная Волынь; не покорствуют ещё новгородцы, отстаивая вечевые права и свободы, но и они уже не решаются призывать к себе князя — он у них только как военачальник, для обороны границ, в делах управления не участвует, — и они не решаются звать князя без ведома Всеволода Юрьевича: Новгород хлебом не богат, торговые пути идут через Владимир, поневоле задумаешься, поневоле смиришься.
— Долгие руки были у батюшки, городки новые рубил в лесных дебрях… И то: срубил городок на речке Москве — Москвой и нарёк город сей; оно так, славы искал: тоже на речке срубил новый городок, так назвал Переяславлем, а речку Трубежем, всё как в южном древнем Переяславле — славу, мол, мы переяли. Так городки-то се были вокруг Владимира. А сынок его Всеволод ишь как расщеперился! Длань свою простер на все пределы русские. Вона как мы, глядите! Гордыня обуяла!
Это о нем так поговаривали, и было тут больше восхищения, нежели ненависти и зависти.
В годы затишья обустраивали и крепили города, возводили каменные храмы, искусные мастера украшали их чудной лепкой и фресками. Белокаменной сказкой разросся на высоком берегу Клязьмы стольный Владимир.
В один из дней Всеволод Юрьевич собрал вместе сынов своих, их у князя много, недаром прозвище ему — Всеволод Большое Гнездо. Сыновья подрастают на диво: старшие, Константин и Юрий, под надзором умудренных в воинском деле воевод уже участвуют в ратных битвах. Они еще отроки, но отец женит их, старается теснее связать удельные княжества родственными узами, хотя знает, как непрочны бывают эти узы — Константина обвенчал со смоленской княжной, Юрия — с киевской, и сам, овдовев, взял дочь витебского князя. Ему скоро стукнет шестьдесят, три с лишним десятка лет из них он — великий князь. Жизнь была сложной, беспокойной, временами его одолевает усталость.
— Живете в княжом дому с оглядкой на меня: батюшка-де голова всему, все решит, все сделает, зачем втягиваться в дела многотрудные? — с такими словами обратился он к княжичам. — Пора вам расправить крылья, не все оставаться птенцами, пора взлететь и соколами. Поедете в земли, какие и вам назначил. Устраивайте свои города и веси, высоким разумом вершите правый суд. А правому бог помощник.