Пізніше, коли полоцькі князі вдруге відмовилися коритися великому князю, Мстислав жорстоко розправився з ними. 1130 р. він наказав Давиду, Ростиславу, Святославу і двом синам Рогволода прибути до Києва з сім’ями на суд, звідки їх заслали до Константинополя. “И всаждавъ ихъ в лодии и поточи их к Царьграду за ослушание ихъ, а по городамъ их посажа мужи своя”. Після цієї акції, згідно з В.Татищевим, Мстислав віддав Полоцьке князівство сину Ізяславу, який до цього сидів у Курську.
Так було покінчено з автономізмом кривицьких князів. “Полоцька операція” свідчила про виняткове посилення влади і авторитету старшого князя Русі. Проти Полоцька Мстислав рушив сили восьми удільних князів, однак сам участі в цьому поході не брав. Не ходив він туди і пізніше, коли полоцькі князі порушили договір. З непокірними розправилися за наказом Мстислава його воєводи. Для вирішення спірних питань між синами Володаря Ростиславича Мстислав також посилав своїх воєвод. Безперечно, так міг чинити тільки великий князь, що мав реальну владу в країні.
Мстислав уважно стежив і за ситуацією, що складалась у північних землях Русі, зокрема в Новгороді. З останнім, де сидів син великого князя Всеволод, Мстислав підтримував постійні і стабільні контакти. Близько 1130 р. він дав дарчу грамоту Юр’ївському монастирю, в якій наказував сину Всеволоду передати монастирю ряд помість з даниною і вирами, за що ігумен Ісая, а також монастирська братія повинні були молити бога за великого князя і його дітей. Дарча грамота одному з багатих і впливових монастирів Новгорода мала на меті зміцнити позиції Всеволода, а отже, і Мстислава у цьому найбільшому місті на півночі країни.
На міжнародній арені Мстислав продовжував політику свого батька, спрямовану на забезпечення непорушності державних кордонів і відстоювання загальноруських інтересів. Насамперед це стосується взаємовідносин Русі з половцями. Дізнавшись про смерть Мономаха, лівобережні половці у 1125 р. напали на Переяславську землю. Обійшовши Переяслав, вони підійшли до міст Баруч і Бронь Княжа в надії на допомогу переяславських торків, розселених у містечках вздовж Трубежа. Назустріч степовикам негайно виступили полки переяславського князя Ярополка Володимировича, які не дали торкам стати на бік половців, після чого ті відійшли в район Посулля. На березі Сули сили Ярополка наздогнали ворожі полки і змусили їх прийняти бій. І хоча, як повідомляє літопис, переяславців було значно менше, вони блискуче виграли бій, багато половців було перебито, інші, тікаючи, потонули у річці.
Наступний переможний похід Мстислав організував близько 1129 р.
Руські полки виступили під проводом воєвод Мстислава і здобули переконливу перемогу над половцями — розгромили їхні численні кочів’я і стани, загнали їх самих “за Донъ и за Волгу, за Яикъ”. Літописець порівнював цей військовий успіх Мстислава з тією перемогою, що її одержав над половцями його знаменитий батько. Після цього половці тривалий час не наважувалися турбувати державні кордони Русі.
Наступальною була політика Мстислава і стосовно інших неспокійних сусідів Русі, зокрема литовців і чуді. Як повідомляє Татищевський літописний звід, руські полки під проводом Мстислава виступили у 1130 р. проти литовців і завдали їм поразки. Літопис не розкриває причин русько-литовського конфлікту, однак можна припустити, що це була відповідь на часті вторгнення литовців у межі Полоцької землі, де в цей час княжив син Мстислава Ізяслав. Матеріали пізніших часів, зокрема XIV ст., свідчать, що литовці мали певні претензії до Новгорода. Суперечності виникали переважно з приводу експлуатації соляних промислів у Старій Русі, які знаходилися в руках новгородських промисловців. Литовці тривалий час безуспішно домагалися мати свою частку в цих промислах, і лише в XV ст., про що ми дізнаємось з торгових договорів Новгорода і Литви, новгородці здають литовцям в оренду дві солеварні. Ще один похід проти литовських племен було здійснено 1132 р., але він не приніс особливих успіхів. Спочатку руські дружини здобули перемогу і навіть проникли в глибинні райони Литви, однак, повертаючись на Русь, частина військ Мстислава потрапила в засідку і була розгромлена.