1197 чи 1198 р. (точнішої дати візантійський історик не подав) половецькі хани вдерлися у дунайські землі Візантії, спустошили їх і наближалися вже до Константинополя. Столиця імперії опинилася під загрозою. Але раптом на ворога з тилу вдарив руський князь Роман і завдав йому нищівної поразки. Половці в паніці кинулися тікати. Візантія була врятована.

Давньоруські літописи знають про два наступних походи Романа Мстиславича до Половецького степу, які він здійснив, уже будучи великим галицько-волинським князем, — у 1202-му й 1204 рр. Вони повідомляють, що 1202 р. половецькі орди як завжди несподівано вдерлися на Переяславщину й Південну Київщину. Певно, Роман заздалегідь довідався про майбутній напад кочовиків, тому що з дружиною й загонами підвладних йому бояр своєчасно перебрався ближче до південних рубежів Руської землі. Коли половці поверталися додому, Роман наздогнав їх за річкою Россю, розбив і відібрав награбоване й полонених. А лютої зими 1204 р. князь зібрав південноруських володарів і стрімко пішов до Половецького степу, розгромив військо ханів і повернувся додому із здобиччю та визволеними з полону руськими людьми. Галицький книжник у посмертній похвалі Романові, наслідуючи найліпші зразки середньовічного красного письменства, патетично вигукнув, що цей князь «кинувся був на поганих (язичників. — Авт.), мов лев, був сердитий, мов рись, і нищив їх, неначе крокодил, і переходив землю їх, мов орел, був хоробрий, неначе тур».

Історики гадають, що на схилі 90-х рр. XII ст. Роман утрутився у війну між Візантією й половцями на прохання її уряду. Напевне, між ним та імператором існувала союзницька угода. Справа не обмежилася одноразовою допомогою. Дружні взаємини тривали й далі. Про це свідчить посольство Романа до Візантії на чолі з Твердятою Остромиричем, яке бачив у Царгороді 1200 р. новгородський паломник Добриня.

Приязні стосунки Романа з візантійським імператорським домом були добре відомі на Русі та за її межами. Інакше не можна пояснити кілька легенд, що виникли навколо імені цього князя та членів його родини. Так, Ян Длугош у XV ст., залежні від нього польські історики XVI ст. та український Густинський літопис XVII ст. повідомляють, що після здобуття учасниками IV хрестового походу Константинополя 1204 р. візантійський імператор Олексій Ангел утік в Галич до князя Романа, котрий прийняв його з великою честю. Ця легендарна версія досі у шані серед істориків та філологів-русистів; її, зокрема, підтримуюі російські академіки Д. Лихачов та Б. Рибаков.

Тим часом з візантійських джерел відомо, що насправді імператор Олексій зник з обложеного хрестоносцями Константинополя влітку 1203 р., якийсь час блукав материковою Грецією, а потім потрапив у полон до одного з ватажків хрестоносців, Боніфація Монферратського, котрий вислав його до своїх володінь у Італії. Згодом колишній імператор звільнився і розпочав боротьбу за владу з главою Нікейської імперії (що виникла на уламках Візантії в Малій Азії) Федором І Ласкарем. У битві поблизу Антіохії Олексія Ангела захопили у полон і ув'язнили в одному з монастирів Нікеї, де він невдовзі помер.

Фантастична історія про втечу візантійського імператора до Галича грунтується на давній версії (бо Длугош запозичив її з якогось не відомого нам давньоруського джерела), що Роман Мстиславич близько стояв до візантійського імператора, був йому другом, і тому Олексій Ангел не бачив кращого місця для порятунку, ніж столиця Галицько-волинського князівства. Напевне, у цій легендарній історії проглядає спогад про дійсну втечу майбутнього імператора Андроніка Комніна до Ярослава Галицького 1164 р.

Певна річ, взаємини з Візантією становили одну з домінант у зовнішній політиці Романа Мстиславича. Однак проза життя змушувала його приділяти увагу більш буденним стосункам із західними сусідами, що завжди були не від того, аби поласувати багатим шматком Романової держави. Князь узяв участь у міжусобній боротьбі між претендентами на загальнопольський престол — синами Казимира Справедливого та їхнім дядьком Мєшком. Згідно розповіді польського хроніста Кадлубка, у кривавій битві на річці Мозгаві 1196 р. допомога Романа Казимировичам вирішила справу на їхню користь. Потому сини Казимира підтримували Романа у змаганнях за об'єднання Галичини й Волині.

Майже одночасно Роман Мстиславич завдав вирішальної поразки спорідненим з литовцями войовничим племенам ятвягів — ось чому автор «Слова про Ігорів похід» оспівав перемоги Романа над «Литвою»! Агресивні й нахабні ятвязькі князьки постійно зазіхали на західні землі Галицько-волинської Русі. Особливо терпіли від них селяни порубіжних земель та городяни прикордонних міст. Як оповідає Київський літопис під 1198 р., волинський князь «ходив на ятвягів мститися, бо вони воювали його волость». За цими скупими словами криється грандіозна перемога Романа над ятвязьким союзом племен — ятвяги перебували на стадії розкладу родоплемінного ладу. Пам'ять про здобутки волинського князя 1198 р. зберігалася в наступних поколіннях. Польський хроніст XVI ст. Мацей Стрийковський доніс до нас народний переказ про те, що Роман запрягав литовських бранців (тобто ятвягів) у плуги. А пізній російський «Докладний літопис» додає до цього: "Один литвин, що в плузі тягнув, навчившись руської мови, сказав: «Романе, Романе, худим (бідним) живеш, Литвою ореш».

Фольклористи знають, що мотив запрягання переможених у плуги є одним з найбільш поширених у давньоруському та й узагалі світовому фольклорі. Навряд чи Роман орав на полонених ятвягах, але цей легендарний переказ відбив велетенський розмах його перемоги над хижими ятвязькими князьками, їхніми