Начало своего княжения юный князь ознаменовал основанием Юрьева монастыря в Новгороде: вместе с игуменом Кириаком, он заложил там в 1119 году величественный храм великомученика Георгия, наделив обитель разными угодьями. По случаю рождения сына Иоанна он построил на торговой новгородской площади, на Петрятином дворище, храм святого Иоанна Предтечи и выдал для нового храма весьма значительную по содержанию грамоту.^>6

Наступило тяжкое время для Новгорода: угнетаемый двухлетним голодом, народ питался липовым листом, березовою корой, соломою и мохом; по улицам лежали трупы, и некому было погребать их; родители отдавали детей своих купцам иноземным, чтобы только спасти их от голодной смерти. В эти горестные дни Всеволод явил всю отеческую любовь свою к народу: он был отцом сирот и вдов, питателем нищих и голодных, истощал на них казну свою, но и ее недоставало для множества просящих.

Пребывая в Новгороде, Всеволод делал походы в Емь (Финляндию) для охранения новгородских границ, в Эстонию и Литву; все эти походы были удачны.

В 1132 году дядя его, князь Ярополк, вступил на киевский престол, дал Всеволоду удел Переяславский, который считался старшим после Киева и служил иногда переходным к великому княжению. С неудовольствием отпустили новгородцы своего доброго князя, упрекая его, что он изменил Святой Софии; а между тем родной дядя его, младший сын Мономаха князь Юрий Долгорукий, вооружился, говоря, что Ярополк хочет сделать племянника наследником своим в Киеве. Утром въехал Всеволод в Переяславль и до обеда выгнан был Юрием. Избегая междоусобия, богобоязненный князь возвратился в Новгород, но там на вече уже не хотели принять его, позабыв благодетельное его правление и славные победы. Спустя два года брат его Изяслав, лишенный удела тем же дядею Юрием, пришел в Новгород просить помощи. Новгородцы зашумели, вызываясь защищать Мстиславичей против властолюбивого Юрия. Всеволод выступил с войском, но поход был неудачен. Новгородцы требовали новой войны, хотели снова идти к Суздалю, но и на этот раз Бог не благословил оружия новгородского. Начали зимний поход, с терпением сносили холод и вьюги, но кровопролитная битва на Ждановой горе (26 января 1135 года) осталась навсегда памятною в летописях: здесь новгородцы потеряли множество людей, побили еще более суздальцев, но не могли одержать победы, и сам Всеволод едва спасся с остатком дружины. «Вся земля Русская разодралась тогда», по красноречивому выражению летописца.

Раздраженные неудачей новгородцы, собравшись на смутное вече, осудили Всеволода на изгнание. Он был заключен в епископском доме с женою, детьми и тещею (супругою святого князя Николы Святоши), семь недель содержался как преступник под стражею и получил свободу только тогда, когда прибыл в Новгород избранный народом князь Святослав Ольгович, друг Юрия.

Добродушный Ярополк дал изгнаннику Вышгород. Жители Пскова, до того времени неразлучные от новгородцев под властию одного князя, дорожили благодеяниями Всеволода и с живым усердием звали его к себе. Всеволод согласился на призыв любви; на дороге имел он утешение видеть, что между князьями его времени не иссякла любовь христианская. Полоцкий князь Василий, вместо того чтобы мстить за обиды, нанесенные ему Великим Мстиславом, принимал и провожал Всеволода с братскою любовию. Верные псковитяне приняли с восторгом призванного ими князя и не устрашились, когда новгородцы поднялись на них войною. Устроив засеки и засевши в окопах, они клялись не выдать своего князя. Одумался Святослав Новгородский, побоялся кровопролития и воротился в Новгород, говоря: «Пусть Бог все управит Своим Промыслом».