Об этом Мстиславе в Начальной летописи также есть интересная легенда, которая нашла себе отражение и в «Слове о полку Игореве»: в самом начале «Слова» вспоминается о том, как старинный поэт Боян, «песнь пояше храброму Мстиславу, иже зареза Редедю пред пълкы Касожьскими». На северном Кавказе находилось русское княжество, центром которого был город Тьмутаракань. Там и княжил Мстислав в соседстве с «касогами» — черкасами. И вот что записано под 1022 годом летописи: «Когда Мстислав был в Тьмутаракани, он пошел против Касогов. Услышавши это, князь Касожский Редедя вышел против него, и, когда оба полка стали друг перед другом, Редедя сказал Мстиславу: „Зачем нам губить дружину? Сойдемся лучше мы сами бороться друг с другом. Если одолеешь ты, то возьмешь и мое имущество, и жену мою, и моих детей, и страну („землю“) мою. Если я одолею, то возьму все твое“. И сказал Мстислав: „Пусть будет так“. И сказал Редедя Мстиславу: „Будем биться не оружием, но будем бороться“. И взялись бороться крепко. Мстислав стал изнемогать, потому что Редедя был велик и силен. И сказал Мстислав: „О Пречистая Богородица, помоги мне. Если я одолею, то построю церковь в Твое имя“. И сказавши это, ударил Редедей о землю и, вынув нож, зарезал Редедю. Вторгнувшись в его сторону, взял все имение его, и жену, и детей и положил дань на Касогов. И, придя в Тьмутаракань, заложил церковь Св. Богородицы и построил ее. Она стоит и до сего дня в Тьмутаракани».
Вероятно, существование обетной церкви в Тьмутаракани послужило сохранению самого события в памяти летописца, внесшего рассказ о нем в начале последней четверти XI века. С другой стороны, событие вызвало былину, песню «дружинного» княжеского поэта, которая поминается еще целый век позднее летописца. Упоминание события в «Слове о полку Игореве» представляет собой кратчайшую заметку, тему, извлеченную из бояновой песни. По существу и рассказ летописи не имеет в основе ничего, превышающего эту тему, только здесь кратчайшая заметка распространена диалогами и монологом, и автор ее, по-видимому из духовенства, особенно отметил обет и церковь. Конечно, все элементы летописного рассказа можно вообразить и как содержание дружинной песни. Действительно, поединок предводителей перед враждебными войсками, по условию их решающий судьбу войны, манера и перипетии борьбы, победа над одолевавшим уже противником, случившаяся по обетной молитве, даже речи на поединке — все эти мотивы встречаются и в устной словесности многих национальностей. Но устная «песня», «былина» имеет свои стилистические особенности, в них именно и сказывается спецификум песенной поэзии, в данном же летописном рассказе нет явного следа этой стилистики. За происхождение рассказа летописи от устного произведения, возможно от песни, говорит только нижеследующее: изображение исторического лица в роли богатыря-поединщика и описание самого процесса боевого подвига такого героя являются для летописи редкостью, тогда как в дошедших до нас русских устных былинах процесс богатырского поединка изображается постоянно и служит обязательной принадлежностью былинного сказа. Вероятно, именно народное представление о Мстиславе отразилось в чертах его портрета, данного летописью при сообщении о его смерти: «бе же Мстислав дебел теломь, чермен лицом, великыма очима, храбор на рати, милостив, любяше дружину по велику, именья не щадяше, ни питья, ни еденья браняще».
Со времени Ярославова единовластия, которым предположительно датируют конец первоначальной «Повести временных лет» (1037–1039), и до второго десятилетия XII века, когда была завершена редактурой дошедшая до нас версия «Повести временных лет», воинскими сюжетами являлись преимущественно княжеские междоусобицы; борьба же Руси с «иноплеменниками» сколько-нибудь литературно изображалась лишь начиная с 60-х годов XI века, когда появились в южнорусской степи половцы, которые лет на полтораста стали главным врагом Руси. Как правило, мы не будем рассматривать повестей о внутренних усобицах; лишь в отдельных случаях привлечем повести об усобицах, особенно если они окажутся интересны стилистически и влиятельны этой стороной. Итак, главным материалом для дальнейшего послужат нам повести о борьбе с половцами как «общим» врагом всей Руси. Повести о борьбе с половцами имеют за собой и то преимущество, что ведут нас к «Слову о полку Игореве».
Первое нападение половцев на Русскую землю летописец отнес к 1061 году, когда они разбили Всеволода Ярославича. В 1067 году половцы разбили на реке Льте всех старших князей: Изяслава Киевского, Святослава Черниговского и Всеволода Переяславского, что вызвало покаянные размышления летописца: «Наводить бо Бог по гневу своему иноплеменьникы на землю, и тако скрушеным им, въспомянутся к Богу; усобная же рать бываеть от соблажненья (или — от съважения) дьяволя» и т. д. Поражение князей сопровождалось усобицей между Ярославичами и Всеславом Брячиславичем Полоцким. «По сем же, Половцем воюющим по земле Русьстеи, Святославу сущо Чернигове, и Половцем воюющим около Чернигова, Святослав же, собрав дружины неколико, изиде на ня ко Сновьску. И узреша Половци идущь полк, пристроишася противу. И видев Святослав множьство их, и рече дружине своей: потягнем, уже нам не лзе камо ся дети. Удариша в коней; одоле Святослав в трех тысячах, а Половец бе 12 тысяче, тако бьеми, а друзии потопоша в Снъви, а князя их яша рукама, в 1 день ноября. И възвратися с победою в град свой Святослав».