Жена: дочь кн. Черниговского Святослава.

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

В 1132 году умер отец Всеволода, Мстислав. Великое княжение наследовал брат его Ярополк. Еще при жизни Мстислав уговорился с Ярополком, чтоб тот немедленно по принятии старшего стола перевел на свое место в Переяславль старшего племянника Всеволода из Новгорода. Распоряжение это вызвало сильное раздражение младших дядей - Юрия Долгорукого и Андрея. Они сказали: "Брат Ярополк хочет по смерти своей дать Киев Всеволоду, племяннику своему", -и поспешили предупредить последнего. Утром въехал Всеволод в Переяславль, а до обеда еще был выгнан дядею Юрием. Не получив стола на юге, Всеволод возвратился в Новгород, но нашел здесь сильное волнение - встань великую в людях, по выражению летописца; пришли псковичи и ладожане в Новгород, и Всеволод должен был выехать из него; потом, однако, горожане скоро одумались и возвратили его назад. Можно, впрочем, с вероятностью полагать, что Всеволод был принят не так уже, как прежде, что здесь положено начало условиям или "рядам" новгородцев с князьями; вероятно также, что с этого времени и посадник переменяет свой характер чиновника княжеского на характер чиновника народного, избираемого от веча, хотя и не без участия князя. С этого времени Всеволод не имел надлежащего значения в Новгороде, не мог заставить его жителей выслать в Киев обычную печорскую дань, за которою великий князь  Ярополк должен был послать другого племянника, Изяслава; последнему удалось взять дань.

В 1134 году Изяслав Мстиславич вновь явился в Новгород с тем, чтобы уговаривать брата и горожан идти войною на дядю Юрия, добыть для Мстиславичей хотя бы Ростовскую волость, если им не нашлось удела в южной Руси. После этого предложения было бурное вече: одни хотели защитить Мстиславичей и добывать им волость, другие нет; большинство оказалось на стороне первых, решено было идти в поход, а несогласных побросали с моста в Волхов, как говорит летописец. Мстиславичи с посадником Петрилой отправились на войну, но едва достигли реки Дубны, как несогласия городского веча повторились в полках: противники похода опять подняли голос и на этот раз пересилили, заставили князя возвратиться и тут же, отняв посадничество у Петрилы, отдали его Ивану Павловичу. Нов Новгороде ждало их поражение: здесь противники их опять пересилили, и опять Всеволод со всею Новгородскою областью пошел на Ростовскую землю. В то время были жестокие морозы и метели. На Ждановой горе новгородцы встретились с ростовскими полками и потерпели жестокое поражение, погибли посадник Иван и многие другие добрые мужи. Возвратясь домой, новгородцы начали еще больше злобиться на Всеволода.

В 1136 году Всеволод Ольгович одержал на юге победу над Ярополком Владимировичем. Противники Всеволода Мстиславича воспользовались этим, чтоб восстать против него. В том же году новгородцы призвали псковичей, ладожани стали думать, как бы выгнать князя. Подумавши, посадили его в епископском дворе с женою, детьми и тещею, приставили сторожей стеречь его день и ночь с оружием по 30 человек на день и не выпускали до тех пор, пока не приехал новый князь, Святослав Ольгович из Чернигова. Вины Всеволода так означены в летописи: 1) не блюдет смердов; 2) зачем хотел сесть в Переяславле; 3) в .битве на Ждановой горе прежде других побежал из. полку; 4) вмешивает Новгород в усобицы: сперва велел приступить к черниговским Ольговичам, а теперь велит отступить.

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

В начале следующего года Всеволод умер и погребен в Пскове в церкви Дмитрия Солунского. Из Жития его можно заключить, что князь этот был добрый и мягкий.