Сын Мстислава Изяславича, киевского князя, а затем князя владимиро-волынского, внук киевского князя Изяслава Мстиславича. Впервые упоминается в Ипатьевской летописи под 1188 г. в связи с занятием им Владимира-Волынского, куда он не хотел пустить ушедшего из Галича брата Романа. Испугавшись угроз Рюрика Ростиславича, Всеволод оставил Владимир и ушел на княжение в Белз. Он умер в 1195 г. 

Всеволод Мстиславич, четвертый сын князя М. Изяславича и Агнесы, дочери польского князя Болеслава III Кривоустого (из Пястов; умер 28 октября 1138 г.). Из Галицко-Волынских Рюриковичей.

Дата и место рождения Всеволода неизвестны. Впервые упоминается в польских источниках в 1182 г. в связи с войной с польским князем Казимиром II Справедливым (из Пястов; умер 5 мая 1194 г.) у р. Западного Буга и г. Берестья.

В 1188 г. Всеволод безуспешно помогает галицкому князю Владимиру Ярославичу против польского князя Казимира и брата Олега; терпит поражение и возвращается в Белз. В том же году получает Владимир-Волынский от брата Романа, который, овладев Галичем, целует ему крест и говорит, что ему «боле ми того не надобѣ Володимерь».

Чуть позднее в этом же году его брат Роман дважды пытается вернуть себе отданный ему Владимир-Волынский. Только в конце года Всеволод, устрашенный угрозами тестя брата, великого князя Рюрика Ростиславича, уступает Роману Владимир; сам удаляется в Белз, где и княжит до своей смерти.

В 1191 г. участвует вместе с братом Романом в междоусобице польских князей, своих дядьев (по матери) — Казимира II Справедливого (из Пястов; умер 5 мая 1194 г.) и Мешко III Старого (из Пястов; умер 13 марта 1202 г.), на стороне первого. В составе польского войска Казимира берет г. Краков.

Всеволод Мстиславич умирает в апреле 1195 г. в Белзе, приняв схиму. Погребен во Владимире-Волынском в соборной церкви Успения Святой Богородицы «со обычными пѣньми». От неизвестной оставил сыновей: Александра и Всеволода.