По временам Большое Гнездо проявлял и суровость, но лишь в особенно вопиющих случаях и никогда не перебарщивал с жестокостью.
В 1178 году Новгород позвал к себе князем Ярополка Ростиславича – того самого, чудесно прозревшего и после этого оставшегося врагом Всеволода. Большое Гнездо был возмущен тем, что новгородцы, целовавшие ему крест на верность, нарушили свою клятву. В наказание он осадил Торжок, принадлежавший Новгороду, и хотел было вынудить его к мирной сдаче, но горожане не желали капитулировать, а дружина требовала от князя жестких мер. Прождав пять недель, Всеволод наконец приказал взять Торжок штурмом и сжечь – но жителей не перебили, как обычно делалось в подобных случаях, а лишь «перевязали», то есть забрали в плен.
Так же тридцать лет спустя великий князь поступил с Рязанью, истощившей его долготерпение. В 1207 году он ходил на эту взбунтовавшуюся область походом, но рязанцы покаялись, и Всеволод повернул обратно. На следующий год они опять подняли мятеж, схватили княжеских представителей и некоторых умертвили, похоронив заживо («засыпали в погребах»). Когда Всеволод пришел с войском, горожане повели себя дерзко. Тогда Большое Гнездо спалил непокорный город, но жителей не истребил, а лишь расселил по другим местам.
Разумное сочетание твердости и умеренности обеспечило Всеволоду Юрьевичу прочное положение первого из владетельных князей, но этого ему было недостаточно. Как его брат Андрей Боголюбский, а перед тем отец Юрий Долгорукий, он не хотел быть первым среди равных, а стремился стать самовластным правителем всей Руси, снимая и назначая удельных князей по своей воле. (Примечательно, что в эту эпоху «Русью» называются только южные области разъединенной страны, а «отчина» владимирских князей числится особо).
Действия Всеволода на «Руси» были успешнее, чем у Боголюбского, потому что Большое Гнездо вел себя осторожнее и дипломатичней, но всякий успех оказывался недолговечным. Задача была невыполнимой.
Владимирский князь обыкновенно выжидал, когда где-нибудь начнется междоусобица или смута, и тогда вмешивался в конфликт, стремясь подчинить себе эту часть страны. В результате получилось, что воевал он практически беспрерывно, часто по нескольку раз с одними и теми же противниками, которые то подчинялись ему, то снова восставали. Все свои незаурядные дарования Всеволод потратил на этот Сизифов труд.
Он без конца замирял соседнюю Рязань; ссорился, мирился и снова ссорился с черниговскими Ольговичами; сходился и расходился со смоленскими Ростиславичами.
Много сил у Всеволода ушло на попытки подчинения Галицкой земли. После смерти Ярослава Осмомысла там начались раздоры, и с 1190 года Всеволод активно в них вмешивался. Двадцать лет, до самого конца жизни, он тщетно пытался присоединить к своему «гнезду» этот дальний регион, но лишь истощил силы и приобрел грозного врага, который в конце концов подорвет мощь Владимиро-Суздальской державы и разорит Всеволодово наследие.