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

Для города он сделал много. Вместе со святителем Нифонтом, архиепископом Новгородским, князь поставил несколько храмов — среди них собор великомученика Георгия в Юрьевском монастыре и церковь Иоанна Предтечи на Опоках, построенная в честь небесного покровителя его первенца Иоанна, умершего в младенчестве. Своим уставом он дал льготные грамоты Софийскому собору и другим церквам. В страшный голод князь истратил на спасение людей всю казну. Воином он был доблестным, ходил с победой на ямь и на чудь, но, как отмечает житие, никогда не брался за меч ради корысти или власти.

После смерти отца дядя перевёл Всеволода в Переяславль Южный, но младшие Мономаховичи выступили против племянника, и князь, не желая усобицы, вернулся в Новгород. Там его встретили холодно: новгородцы считали, что вскормили князя и уходить он не смел. Неудачный зимний поход на Суздаль решил дело — вече осудило Всеволода на изгнание. Полтора месяца князя с семьёй держали под стражей на архиерейском дворе, а потом выпустили из города. Церковь и сегодня величает его исповедником; в тропаре о нём поётся: «изгнание претерпел еси от своих».

В 1137 году псковичи, помнившие князя по совместным походам, сами призвали его к себе — он стал первым псковским князем, избранным по воле самого города. Главным его делом во Пскове стала постройка первого каменного храма во имя Живоначальной Троицы на месте деревянного, стоявшего здесь ещё со времён равноапостольной Ольги. Поэтому на иконах князя часто пишут с храмом в руке.

Княжил он всего год: скончался 11 февраля 1138 года, прожив сорок шесть лет. Весь Псков вышел на погребение, и церковного пения не было слышно за народным плачем. Новгородцы, опомнившись, прислали за телом, но рака не двинулась с места; тогда они просили дать хоть малую частицу праха «на утверждение граду». У гроба князя положили его щит и меч в форме креста с латинской надписью «Чести моей никому не отдам». В 1192 году мощи обрели и перенесли в Троицкий собор, а в 1834 году, в первый день Пасхи, — в главный храм собора.

Псков считает его своим чудотворцем. Во время осады города Стефаном Баторием в 1581 году, когда крепостная стена уже была разрушена, мощи князя крестным ходом принесли на место сражения, и приступ был отбит; в ряды защитников выносили и его икону. Память благоверного князя совершается трижды в году: 24 февраля, 5 мая и 10 декабря.