Неизвестно заключал ли при этом Тмутараканский князь какие-либо формальные или неформальные соглашения с Византией, но, во всяком случае, он полностью использовал благоприятный для него факт начала византийско-грузинской войны.
Когда княжеское войско встретилось с войском аланов и касогов, то, согласно летописным данным, касогский царь Редедя вызвал Мстислава на поединок следующими словами: «Чего ради погубим дружины? Но сойдемся, чтобы побороться самим. Если одолеешь ты, возьмешь богатства мои, и жену мою, и детей моих, и землю мою. Если же я одолею, то возьму твое все». Кроме того, Редедя предложил бороться без оружия, на что Мстислав ответил согласием.
Подобные поединки полководцев были вполне в духе времени и воспринимались современниками как высшее проявление воинской доблести. Думается, позволительно сравнить их со знаменитым «бусидо» (путем воина) – неписаным кодексом чести самурая.
Летописец рассказывает похожую историю о противоборстве князя Владимира Святого с печенежским князем в 992 г. Последний предложил крестителю Руси поединок лучших воинов: «Выпусти ты своего мужа, а я своего – пусть борются. Если твой муж бросит моего на землю, то не будем воевать три года. Если же наш муж бросит твоего оземь, то будем воевать три года».
Редедя был сильнее Мстислава и тогда, как рассказывает летопись, Мстислав воззвал: «О, Пречистая Богородица, помоги мне! Если же одолею его, воздвигну церковь во имя Твое». После этого он сумел ударить об землю и убить ножом (против поверженного оземь противника уже можно было применять оружие) князя касогов, и войско последнего сдалось без боя. Необходимо отметить, что в данном случае не приходится говорить об излишней жестокости к поверженному противнику: согласно древнему обычаю, поверженного врага убивали.
У нас нет оснований сомневаться в точности летописных данных (что, конечно, не исключает наличия в них некоторой доли художественного вымысла в деталях). Например, косвенным подтверждением правдивости изложения поединка Мстислава и Редеди служит то, что после одержанной победы тмутараканский князь построил в своей столице церковь Пресвятой Богородицы (в это время Тмутараканская епархия стала епископальной), ставший первым русским каменным храмом в Крыму. Заметим, что Мстислав в дальнейшем построил храмов больше, чем любой из современных ему князей (разве что за исключением Ярослава Мудрого) и внес огромный вклад в процесс христианизации Киевской Руси, в которой долгое время после крещения были сильны пережитки язычества. Понятно, что столь активное храмовое строительство было возможно лишь при отсутствии серьезной внешней угрозы.
Показательно, что поединок Мстислава с Редедей навсегда остался в народной памяти в качестве символа национальной победы над опасным врагом. Неслучайно о Мстиславе говорится в самом начале «Слова о полку Игореве» как об одном из главных героев Киевской Руси, которого воспевал легендарный сказитель Боян. Процитируем упомянутый отрывок