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