Сын князя Всеволода Игоревича. Впервые он упоминается в «Повести временных лет» под 1097 г., когда вместе с дядей Давыдом Игоревичем бежал из Владимира-Волынского. Около 1100 г. «выиде Мстислав от Давыда на море месяца июня в 10». В. Н. Татищев передает этот факт так: «Иуниа 10-го Мстислав, сыновец Давыда Игоревича, ушел в море для перенятия купцов». Умер он около 1113 г. В. Л. Янин, основываясь на одной из редакций «Хождения игумена Даниила», где среди других русских князей упомянут и Андрей-Мстислав Всеволодич, а также на материалах «Повести временных лет» и системе старшинства, существовавшей в начале XII в. на Руси, высказал мысль о том, что Смоленск примерно с 1102–1103 гг. принадлежал не Мономашичам, а Мстиславу-Андрею Всеволодичу. По мнению В. Л. Янина, Мстислав в конце XI в. жил на Волыни, а в 1103 г. «он уже княжил в Смоленске, так как это следует из перечисления князей под 1103 г.». Исследователя не смутило известие о княжении в Смоленске в начале XII в. князя Святослава Владимировича — сына Владимира Мономаха. Он отметил, что княжение Святослава в Смоленске приходится на конец жизни Мстислава Всеволодича, который «мог тяжело болеть, принять схиму и т. п.». После его смерти Смоленск «превратился в вымороченный удел» и перешел к верховному собственнику земли Владимиру Мономаху. Гипотезе В. Л. Янина противоречат известия В. Н. Татищева, согласно которым Смоленская земля после Любечского съезда стала собственностью рода Мономаха. Татищевские сведения, правда, другими источниками не подтверждаются, но и опровергнуть их также невозможно. Как нам хорошо известно, принцип старшинства в XI–XII вв. на Руси не всегда выдерживался, поэтому вряд ли им целесообразно руководствоваться. Нам представляется, что Мстислав в начале XII в. имел какой-то небольшой удел на Волыни. В пользу этого, на наш взгляд, свидетельствует то, что его дядя Давыд Игоревич не участвовал ни в Долобском съезде князей, ни в последовавшем после него походе на половцев. И летописец не усмотрел в этом никакого криминала, хотя и осудил отказ Олега Святославича принять участие в походе на «поганых». Данное обстоятельство может быть объяснено тем, что Давыда Игоревича на съезде и в походе представлял его племянник Мстислав, который и упомянут «Повестью временных лет» под 1103 г.