Мстислав происходил из рода Мономашичей. Его отец Мстислав Ростиславич Храбрый в разное время занимал столы Белгорода, Смоленска и Новгорода. В последнем он умер летом 1180 г. На страницах летописи Мстислав Мстиславич впервые появляется под 1193 г. в качестве удельного трепольского князя. Тогда он в союзе с сыном Рюрика Ростиславича Ростиславом по просьбе Черных Клобуков двинулся на половцев и победил их: «И ополонишася Ростислав и Чернии Клобуце скотомь и коньми, и челядью, и колодник много изимаша, княжичев их и добрый мужи имаша». В 1204 г. Роман Мстиславич разгромил половцев, и скупое известие Суздальской летописи этого года позволяет думать, что в его походе принял участие наш герой: «Ходиша Рустии князи на Половци: Рюрик Киевьский, врослав Переяславь- ский, великого князя Всеволожа сын, Роман Галицкий и Мстиславич (курсив наш. — Н. К.), и иные князи. И взяша Рускии князи полону много, и стада их заяша, и возвратишася во свояси с полоном многим». Это единственный известный из источников поход на половцев, в котором плечом к плечу сражались Роман Мстиславич и Мстислав Мстиславич. Возможно, эта победоносная кампания и отразилась в обращении «Слова» к обоим князьям.

Но вскоре после блестящей победы над половецкими ханами Роман Мстиславич погиб под польским городом Завихостом (1205 г.), оставив после себя громкую славу великого воина и двух малолетних сыновей: четырехлетнего Даниила и двухлетнего Василько. Галицко-Волынское княжество на многие годы делается предметом спора между западными соседями, венгерскими и польскими феодалами, его раздирают боярские свары. К исходу второго десятилетия XIII в. Галич и Галицкая земля оказываются в руках венгерского короля Андрея. В Перемышльской земле хозяйничали польские захватчики, а Романовичи владели лишь г. Владимиром и частью Волынской земли.

Вероятно, не будет преувеличением сказать, что за минувшие после гибели Романа полтора десятилетия в Галицкой Руси, наиболее богатой части Галицко-Волынского княжества, по существу не было князя: короткое княжение девятилетнего Даниила (1211 г.) было лишь эпизодом, а сыновья героя «Слова» Игоря Святославича (Владимир, Святослав и Роман) не сумели закрепиться в Галиче и других городах земли.

Поэтому когда авторитетный новгородский (с 1210 г.) князь Мстислав Мстиславич Удатный выразил желание сесть в Галиче, население Галицкой земли (следует думать, что не только бояре и верхушка городов, но и широкие народные массы) положительно отнеслось к этому. У Мстислава была репутация человека, способного защитить землю от врагов, в чем больше всего нуждались галичане. Он успешно сражался с половцами. В течение 1210— 1212 гг. Мстислав осуществил из Новгорода несколько удачных походов на чудь, т. е. эстов.