Сын великого князя киевского Мстислава Романовича Старого. В 1214 г. Всеволод был посажен князем во Пскове своим двоюродным дядей галицким князем Мстиславом Удалым. Вместе с ним он отправился к берегам Варяжского (Балтийского) моря в поход против племени чудь. В 1216 г. Всеволод был послан отцом в Суздальскую землю, где вспыхнула усобица между детьми великого князя Всеволода Юрьевича Большое Гнездо. В борьбе за Великий Новгород, вместе с Мстиславом Удалым, выступил против переяславского князя Ярослава Всеволодовича. Завоевав симпатии новгородцев, Всеволод Мстиславич вместе с их ратью напал на Ригу, занятую немецкими рыцарями. В 1219 г. новгородцы избрали его своим князем, но вскоре Всеволод был свергнут сильной партией во главе с посадником Твердиславом, тяготевшей к союзу с владимиро-суздальскими князьями. В течение последующих 20 лет Всеволод Мстиславич не играл сколько-нибудь заметной политической роли. В 1239 г. его прежний соперник – Ярослав Всеволодович, ставший великим князем владимирским, разгромил вторгшихся на Русь литовцев, изгнал их из Смоленска и посадил на княжеский стол Всеволода Мстиславича.
В 1280 – 1290-е гг. на Руси разразилась междоусобная война между потомками князя Александра Ярославина Невского. Каждый из них привлекал на свою сторону ордынские войска и рати других русских князей. Федор Черный поддерживал Городецкого князя Андрея Александровича, не раз вместе с ним ходил в походы на русские земли. В ходе войны Федор Черный вернул себе Ярославль, в 1293 г. участвовал в страшной для Руси татарской «Дюденевой рати», разорившей 14 городов.
Похоронен в ярославском Спасо-Преображенском монастыре. Вместе с отцом позднее были похоронены и его сыновья, Давыд и Константин.
В марте 1463 г. мощи князей были открыты и, по церковному преданию, возле них сразу же произошли чудеса – исцелились священник и его сын, прозрели две женщины. Вскоре было установлено местное почитание святых князей. Общерусское их прославление началось в сер. 16 в. День памяти Федора, Давыда и Константина: 19 сентября (2 октября).
Владимир Андреевич содействовал Дмитрию Ивановичу в обороне Москвы от набегов литовского князя Ольгерда (1370,1379 гг.), на дочери которого, Елене, он был женат, в защите Пскова от рыцарей Ливонского ордена (1369 г.), в походе на Тверь (1370 г.). В Куликовской битве 1380 г. командовал засадным полком, решившим исход сражения в пользу русского войска, после чего и получил прозвище Храбрый. В 1382 г., участвовал в сражении у Волока Дамского, против хана Тохтамыша.