Выбыв позднее из борьбы за Киев, Мстислав оказался надолго втянут в политические дела Северо-Западной Руси, прежде всего Новгорода. Здесь с 1205 г. сидел сын владимирского князя Всеволода Большое Гнездо Константин, опиравшийся на группировку Мирошкиничей. В 1209 г. в условиях обострившейся политической борьбы в городе на Волхове Всеволод посадил Константина князем в Ростове, а вместо него отправил младшего сына Святослава. Противники Мирошкиничей Михалковичи задумали изгнать его и, видимо, тайно обратились с предложением о союзе к Мстиславу. Тот напал на Торжок, схватил там дворян Святослава Всеволодовича и его наместника и отправил послов в Новгород, официально предложив им свою помощь:
Пришьл есмь к вам к вам, слыша насилье от князь, и жаль ми своея отцины.
Ведь здесь княжил и умер в 1180 г. его отец. После этого противники Святослава восстали и арестовали Святослава вместе с боярами. Мстислав, принятый в качестве князя новгородцами, собрал ополчение и вновь двинулся к Торжку, готовясь встретить суздальские полки. Всеволод, очевидно, не готовый к схватке с Новгородом и Мстиславом, за которым стояли Ростиславичи, предпочел мирное соглашение и обменял схваченных им было новгородских купцов с их товарами на Святослава и его людей.
Став князем новгородским, Мстислав обратился к делам прибалтийским. В это время Орден меченосцев, завершивший покорение Ливонии, готовился к захвату Эстонии, после чего на очереди оказывались новгородско-псковские земли. Наилучшим способом избежать такого варианта событий было создать сферу своего влияния в землях эстов. В 1209 г. Мстислав направил посадника Дмитра Якунича с отрядом новгородцев в Великие Луки, велев ему «ставить города» (т. е. укрепленные пункты) на границе с Орденом. Затем он сам проинспектировал границу, побывал в Торжке, Торопце, а потом прибыл к Дмитру в Великие Луки. Здесь Мстислав договорился со своим братом Владимиром, князем псковским, о совместном походе в земли чуди. В 1212 г. их рати вторглись в Унганию близ Дерпта (Юрьева), нанесли поражение местным князькам, захватили множество пленников и скота, а затем после восьмидневной осады взяли Медвежью Голову (Оденпе). Побежденных обложили данью и начали обращать в христианство по православному обряду…
В боях, походах и осадах на северо-западе, юго-западе и юге прошло еще несколько лет. Хитросплетения древнерусской политики вокруг Новгорода, Галича, Киева разрубались мечом. Мстислав Удатный приближался к своей главной победе и одной из крупнейших битв в истории междоусобных войн Древней Руси.