Родителями Всеволода были князь Мстислав Великий и Христина, дочь короля Швеции Инге I Старшего. Детство и возмужание юного княжича проходили в Новгороде. Всеволод во всём помогал отцу, готовясь к самостоятельному княжескому служению. И когда князь Мстислав был переведён в Белгород для последующего вступления на великокняжеский престол, Всеволод остался княжить в Новгороде.
Правление князя Всеволода было продолжением отцовского дела: забота о процветании Господина Великого Новгорода, защита от врагов и духовное просвещение.
При нём был возведён величественный белокаменный Георгиевский собор Юрьева монастыря, церковь Иоанна Предтечи на Опоках в честь рождения сына-первенца Иоанна. А когда случился голод, милосердный князь истощил всю свою казну на закупку продовольствия для новгородцев.
Князь Всеволод был доблестным воином. Он победоносно совершил военные походы на беспокойные соседние племена ямь и чудь. Но всегда старался решать дело миром.
Перед своей кончиной великий князь Мстислав завещал престол Киевский своему брату Ярополку, взяв с него обещание перевести Всеволода в Переяславль с прицелом на последующее первоочередное вступление на великое княжение. Ярополк выполнил обещание. Всеволод, не смея ослушаться великого князя, прибыл в Переяславль, откуда, как правило, следовало восхождение на престол. Однако этому воспротивились старшие Мономаховичи во главе с Юрием Долгоруким. Чтобы избежать кровопролития, Всеволод решил вернуться. Но тут возмутились новгородцы. Они считали, что «вскормили» князя Всеволода для Новгорода, и потому укоряли его за нарушение своих обязательств. «Ходил Всеволод в Русь, в Переслав, а целовал крест новгородцам, сказав: “Хочу у вас умереть”».
Чтобы замириться с новгородцами, Всеволод вновь ходил в 1134 году в поход на чудь и вернул во владение Новгорода старинный Юрьев. Этот город основал его прапрадед Ярослав Мудрый. Но затем он был сожжён местными эстонскими племенами. В те времена военные походы считались обязательными для князя. От их успешности во многом зависело отношение к правителю. Следующий поход был направлен в суздальские земли. Противостояние Новгорода и Суздаля положило начало долгой кровопролитной борьбе за верховенство. Суздальцы обложили товары новгородских купцов большим налогом. Новгородцы требовали наказать неучтивых соседей. Большое войско возглавили Всеволод вместе со своим братом Изяславом, которого также не пустил в Переяславль всё тот же Юрий Долгорукий. У Жданой горы (на половине водного пути из Новгорода в Суздаль) рати сошлись. Никоновская летопись сохранила сведения о сём походе: «Того же года, зимой, князь Всеволод Мстиславич иде ратью с немцами и со всею силою Новгородскою на Суздаль и… мужей Новгородцев побиша, и много крови христианской пролишася. И бежаша Новгородцы со князем их к Новугороду, и начаша молвити о Суздальской войне на князя Всеволода Мстиславича; он же умыслил бежати в Немцы».
Неудачный поход ещё более осложнил положение Всеволода. Новгородцы начали вести переговоры с князем Святославом из рода Олеговичей. На следующий год собралось вече, на котором князю Всеволоду припомнили всё. Разгневанный посадский люд заточил всю семью князя под стражу в епископских покоях. «Изгнание еси претерпел от своих», – поётся в тропаре князю Всеволоду. Лишь по прибытии в Новгород князя Святослава Олеговича «пустиша из города».
Всеволод выехал в Киев. Великий князь Ярополк выделил ему «в держание» Вышгородскую волость. Место, где жила великая княгиня Ольга, «градов Киева и Пскова изрядная добро– то». Видно, по молитвам своей великой прародительницы Всеволод был приглашён на княжение во Псков. Псковичи помнили успешные совместные псковоновгородские походы.
Всего год суждено ему было править в славном Пскове. За это время в древнем граде был заложен первый каменный храм. Деревянный собор Живоначальной Троицы был построен ещё княгиней Ольгой. При Всеволоде на его месте был выстроен уже каменный «об одном верху». На иконах святого князя Всеволода изображают с однокупольной церковью в одной руке и мечом в другой.
В этом соборе молился перед Ледовым побоищем князь Александр Невский. Здесь же был крещён князь Довмонт Псковский. Сюда был положен после его кончины крестообразный меч князя Всеволода с надписью «Чести моей никому не отдам».
Князь Всеволод предал Богу душу 11 февраля 1138 года. Весь Псков собрался на погребение полюбившегося им князя. «И не было слышно церковного пения от плача народного», – восклицает летописец. Новгородцы раскаялись и прислали протопопа из Софийского собора, чтобы забрать святое тело. Но князь «отвратился». Горько плакали новгородцы и молили даровать им хотя бы частицу святых мощей «на утверждение граду». По их молитвам отпал ноготь с руки князя Всеволода.
Тело князя Всеволода было положено в храме великомученика Димитрия.