Сын Мстислава Владимировича, внук Владимира Мономаха. В крещении — Гавриил.

В 1117 был посажен отцом княжить в Новгороде и прокняжил там до 1132. Ярополк Владимирович, став великим князем Киевским, перевёл своего племянника в Переяславль, но этому воспротивился Юрий Долгорукий Суздальский, который не желая уступать старшинство племяннику, выгнал его из Переяславля, да и сами новгородцы были недовольны этим переводом.

Во время похода с отцом на чудь 23.01.1131 потерпел поражение в Клине. В следующем походе князь с новгородским войском 9.02.1133 взял Юрьев.

Всеволод при поддержке новгородского посадника Константина Микульчича в 1132 вернулся в Новгород, но в 1136 в городе вспыхнул мятеж: князю припомнили и то, что хотел обменять Новгород на Переяславль, и что бежал с поля битвы во время сражения с суздальцами на Жданой горе. Полтора месяца князь с женою, тещей и сыновьями сидел в заточении на епископском дворе, после чего его изгнали из города. Это событие принято считать началом Новгородской республики.

Всеволод после изгнания оправился в Киев к Ярополку, и получил от него Вышгород.

В этом же году присланный в Новгород на княжение Святослав Ольгович был едва не убит сторонниками Всеволода и посадник Константин Микульчич направился в Вышгород к Всеволоду и уговорил его идти в Псков. В 1137 псковичи приняли Всеволода своим князем, но когда в Новгороде узнали, что Всеволод княжит в Пскове и хочет сесть у них в Новгороде, отправили туда войско во главе со Святославом, который призвал на помощь брата Глеба с курянами и половцами.

В разгар конфликта Всеволод умер 11.02.1138 и был погребён в Свято-Троицком кафедральном соборе Пскова.

Всеволод Мстиславич известен уставной грамотой "Ивановское сто", данной им общине купцов, торговавших воском и мёдом. В этой грамоте впервые упоминается мера веса — пуд.