Всеволод сломил сопротивление старого боярства и стал распоряжаться делами княжества столь же самовластно, как Андрей Боголюбский. Многие его враги из числа ростовских бояр погибли, другие попали в плен и лишились своих сел и конских табунов. Всеволод сурово карал соседей. Когда рязанские князья привели половцев и разграбили Владимир, Всеволод разгромил их, а пленного князя Глеба заточил в тюрьму, где держал до его смерти. Рязанские князья были надолго приведены в послушание.

Южнорусские князья, погрязшие в усобицах, искали помощи и покровительства могущественного северного соседа. Однако Всеволод остерегался посылать крупные силы на юг. В похвалах «Слова о полку Игореве» слышится затаенный упрек великому князю Всеволоду: «не мыслию ти перелетети издалеча отня злата стола поблюсти!» Суздальские князья «не блюли» киевский стол и не обороняли киевских границ от нападений кочевников. Если бы владимирский князь выступил в поход, то много половчан стало бы пленниками: «Аже бы ты был, от была бы чага по ногате (мелкая монета. — Р. С.), а кощей (мальчик–половчанин. — Р. С.) по резане».

Ввиду явного упадка Киева Всеволод искал новую опору для великокняжеской власти. Такой опорой мог быть только Новгород Великий, давний соперник Киева, избежавший половецкого разорения и раздела между князьями. Суздальцы постоянно теснили новгородцев, проникали в Заволочье, где проходили пути из Новгорода в Приуралье, не раз захватывали Новый Торг, служивший главным перевалочным пунктом в торговле с «Низовской землей». И Юрий Долгорукий, и Андрей Боголюбский многократно сажали своих сыновей и подручных князей в Новгороде. Но только Всеволод пришел к мысли о перестройке всей системы великокняжеской власти на Руси. Отпуская старшего сына Константина на новгородский престол в 1206 г., Всеволод произнес речь: «сыну мой Костянтине, на тобе Бог положил переже старейшиньство во всей братьи твоей, а Новгород Великий старейшиньство имать княженью во всей Руськой земли». По мысли князя, владеть Новгородом, как прежде Киевом, мог отныне только Владимир, что давало владимирскому князю старейшинство «в всей Русской земли».

Судя по летописям, Всеволод был первым суздальским государем, прочно усвоившим титул «великого князя». Передача Новгорода наследнику создала новый центр власти, вызвавший беспокойство монарха. Без видимых причин отец свел сына из Новгорода, а взамен дал «старейшему князю» города Ростов, Ярославль и Белоозеро. Ранние летописи ничего не сообщают о «ряде», данном Всеволодом своим сыновьям. Вероятно, князь умер скоропостижно и не успел выразить последнюю волю. Как всегда, решающее слово в периоды междуцарствий принадлежало боярам. Младшие братья Юрий и Ярослав объединились против старшего Константина. Но им и их боярам пришлось дважды снаряжаться в поход, прежде чем Константин отказался от прав на владимирский престол и заключил с братьями «поряд».

Южнорусские князья не желали мириться с утратой Новгорода. В 1210 г. сын Мстислава Храброго Мстислав Удалой выгнал из Новгорода малолетнего сына Всеволода. Несколько лет спустя Мстислав покинул Новгородскую землю и уехал в Киев. Если бы новгородцы захотели восстановить прежние отношения с Суздальской землей, им пришлось бы принять князя из рук Юрия Владимирского. Однако они пригласили князя Ярослава из Переяславля, зятя Мстислава Удалого. Ярослав пытался использовать внутренние раздоры в новгородском обществе, чтобы утвердить свою власть над Новгородом. В результате ему пришлось покинуть город и укрыться в Торжке, откуда он пытался продиктовать новгородским боярам свои условия.