Уже перший рік княжіння Мстислава показав, що він досяг визнання свого старшинства усіма князями Русі. До нього як до голови держави зверталися князі інших династій по допомогу і за сприянням у вирішенні “внутрішніх” справ. 1126 р. Мстиславу, як свідчить Татищевський літописний звід, довелося втрутитись у справи галицьких князів. Після смерті Василька і Володаря Ростиславичів (близько 1124 р.) Галицька земля перейшла до рук їхніх синів. Ростислав Володарович — як старший — сів у Перемишлі, Володимирко Володарович — у Звенигороді, Васильковичі (Ігор і Ростислав) зайняли відповідно Галич і Теребовль. Поділ Галичини на чотири частини загрожував спалахом нових усобиць, які й почалися 1126 р. Володимирка не задовольняла роль другорядного князя землі, і він почав підготовку до війни з братом Ростиславом, попередньо заручившись підтримкою угорців, з якими перебував у близьких родинних стосунках,— його дружиною була дочка угорського короля. Ростислав звернувся по допомогу до великого князя Мстислава і двоюрідних братів. Під час мирних переговорів у Щирці, які відбулися на вимогу великого князя, ворогуючі сторони так і не змогли домовитися. Ростислав виступив на Звенигород і обложив його; Володимирко з дружиною втік до тестя. Під загрозою втрати столу він врешті змушений був припинити ворожнечу з братами: “Более на брата воевать не смел, ведая, что Мстислав может его всего лишити”.
Незабаром Мстиславу Володимировичу довелося зайнятися чернігівськими справами. У 1128 р. з далекої Тмутаракані виступив на Русь Всеволод Ольгович. Швидким маршем він підійшов до Чернігова і заволодів ним. Ярослав Святославич, не маючи сил для боротьби з сильним і енергійним племінником, змушений був погодитися на обмін волостями із Всеволодом і відійшов до Тмутаракані. Дуже швидко він, очевидно, пошкодував про свою поступливість і, перейшовши до Мурома, направив великому князю грамоту з проханням відновити справедливість: “Хрестъ еси цѣловаль ко мнѣ, поиди на Всеволода”. Вірний політиці мирних взаємовідносин, Мстислав робить спробу умовити Всеволода повернути Чернігів Ярославу. Але вона виявилась безуспішною, і великий князь почав підготовку до походу на Чернігів. А Всеволод тим часом призвав на допомогу половців. Семитисячний корпус на чолі з воєводами Ставшем і Селуком виступив на Русь. Від давньоруського міста Вир половці направили до Чернігова послів, а самі заходилися грабувати міста і села Переяславської землі. По дорозі до Всеволода половецькі посли потрапили в засідку і були взяті в полон. Не одержавши від чернігівського князя жодних вістей, Селук і Ставш вирішили залишити межі Русі: “Половци же вземше вѣсти отъ Олговичъ бѣжаша усвояси”.
Всеволод, розуміючи, що не зможе протистояти дружинам Мстислава, вдається до підкупу найвпливовіших радників великого князя, і ті відмовляють його від походу на Чернігів. Ігумен монастиря св. Андрія Григорій, який користувався особливою симпатією і повагою ще у Мономаха, знімає з Мстислава хресне цілування з Ярославом, причому зазначає, що в даному випадку Мстислав бере на душу гріх значно менший, ніж тоді, коли піде походом на Всеволода і проллє кров християнську. Мстислав послухався ігумена Григорія, однак, як свідчить літопис, до самої смерті шкодував про це. Втративши підтримку Мстислава, Ярослав повернувся до Мурома, де і помер у 1130 р.
Результатом участі Мстислава в чернігівській усобиці було приєднання до великокняжих володінь Посейм’я, яке, вірогідно, йому віддав Всеволод як нагороду за нейтралітет.
Набагато рішучіше повів себе Мстислав щодо полоцьких князів, які роблять спробу повернути собі Мінськ, Друцьк та деякі інші володіння, приєднані до великокняжих земель ще Мономахом. У відповідь Мстислав рушив проти Полоцька сили багатьох князівств. Чотирма шляхами наступали вони на Полоцьку землю: В’ячеслав з Турова, Андрій з Володимира, Всеволодко з Гродна і В’ячеслав Ярославич з Клечська. Всі вони мали з’єднатися з полками Ізяслава Мстиславича. Всеволоду Ольговичу Мстислав наказав прибути до Борисова, Івану Воїтишичу з торками і Ростиславу із смоленським полком — до Друцька. Новгородські сили на чолі з Всеволодом Мстиславичем повинні були вийти до Неклоча. Для всіх князів призначався єдиний день наступу на Полоцьк. Полочани змушені були вжити термінових заходів, щоб врятувати місто, — вони звинуватили в усьому князя Давида і його синів, вигнали їх з Полоцька і звернулися до Мстислава з проханням утвердити на полоцькому столі князя Рогволода.