Поединок начался не в пользу Мстислава. Могучий Редедя стал давить его к земле. Мстислав был уже христианином. Известно его крестильное имя — Константин. Русский князь стал молиться Богородице, чтобы даровала ему победу. Обещал воздвигнуть в ее честь храм в Тмутаракани. В итоге он выиграл, сумев зарезать своего противника ножом «перед полками касожскими».
«И нача изнемогати Мстислав, бо бе велик и силен Редедя, и рече Мстислав — «О пресвятая Богородица, помози ми, аще бо одолею сего, съзижду церковь во имя твое». И рек се, удари им оземлю, и вынзе нож и зареза Редедю».
«Повесть временных лет».
Обещание свое Мстислав выполнил. Археологи нашли в месте, где некогда стояла Тмутаракань, остатки фундамента Богородичной церкви.
Победа над Редедей положила конец войне 1022 г. Как и требовал древний обычай, победитель получил власть над землей и подданными проигравшего Редеди. Мстиславу досталась и семья яско-касожского вождя, но с ней он обошелся по-рыцарски. Жена и два сына Редеди жили при князе и входили в тмутараканскую элиту. Мстислав стал крестным отцом сыновей Редеди. В крещении они приняли имена Юрий и Роман. Последний стал зятем Мстислава, женившись на его дочери Татьяне. От этой пары вели свое происхождение (скорее всего, мифическое) несколько московских аристократических родов — Белеутовы, Добрынские, Сорокоумовы-Глебовы.
Власть Мстислава над ясами и касогами значительно увеличила военные возможности тмутараканского правителя, и он решил вмешаться в борьбу за отцовское великокняжеское наследство. Великий князь Владимир умер в 1015 году. Никакого четкого порядка престолонаследия на Руси еще не выработалось, с момента кончины Владимира и до 1019 г. шла на Руси усобица между его сыновьями. Летописи приписывают Святополку, старшему сыну или племяннику Владимира, убийство братьев — Бориса и Глеба, а также намерение истребить всех своих братьев-соперников. Однако Ярослав, князь новгородский, оказался удачливее и сильнее Святополка. В 1016 и в 1019 гг. с помощью новгородцев и варягов он разбил Святополка, и тот, бежав на Запад, там и сгинул.
Мстислав Храбрый против Ярослава Мудрого
До 1022 г. у Ярослава никто не оспаривал киевский стол, и он считался великим князем, хотя в 1021 г. ему и пришлось повоевать с племянником Брячиславом Изяславичем Полоцким, напавшим на новгородские земли. Возможно, эта выходка Рогволожьего внука побудила и Мстислава Тмутараканского вспомнить о своих правах наследника. В 1023 г. Мстислав во главе тмутараканской дружины и яско-касожского войска появился на левой Северской стороне Днепра. Он захватил Чернигов. Здесь его войско пополнилось черниговскими полками.