В 1022 г. Мстислав устранил одного из соседей — князя Редедю. По летописи, дело было так: Мстислав пошел на касогов. И когда два войска стали друг против друга, Редедя великодушно предложил Мстиславу не губить бойцов, а сойтись без оружия в единоборстве. И ответил Мстислав: «Пусть будет так». «И схватились крепко, и долго боролись, и стал Мстислав изнемогать, потому что Редедя был большой и сильный». Тогда взмолился Мстислав: «О, Пречистая Богородица, помоги мне! Если я его одолею, то построю церковь во имя твое». Вынул ножик из-за голенища и зарезал простодушного Редедю. «И пошел в его землю и взял его достояние и жену его, и детей его и наложил дань на касогов. А вернувшись в Тмутаракань, заложил церковь Пресвятой Богородице и построил ее».
Петербургский ученый XVIII в. И. К. Тауберт считал подданных Редеди казаками. Летописцы называли их касагами, касогами, казягами. Все они пополнили войско Томаторкани, сформированное ранее из казар Приазовья.
В 1023 г. Мстислав захватил Северское княжество и Чернигов. Однако его старший брат Ярослав, князь Новгорода и Киева, не пожелав расстаться с сим изобильным краем, собрал дружины, усилив их наёмными варягами из Скандинавии, и пошел войной на брата.
Но кавказцы Мстислава разгромили их. Эту битву под Лиственом летописец осветил довольно поэтично: «И была ночь, и была тьма, молния, и гром, и дождь». Варяги много потрудились, убивая северян, но потом бойцы Мстислава стали рубить наемников. При вспышках молний блестело оружие, ревела буря, гром гремел, шла страшная рубка. И среди всего этого столпотворения красовался варяг Якун в золотых доспехах. Ярослав, увидев, что его побеждают, подался в бега вместе с Якуном — князем варяжским. Тут-то Якун и потерял свои золотые латы.
Ярослав бежал в Новгород, а Якун — за море варяжское. Мстислав же на рассвете, увидев побитых варягов и северян Ярослава, сказал: «Кто же этому не был бы рад?! Вот лежит северянин, вот — варяг, а своя дружина цела!»
После разгрома под Лиственом Ярослав долго не решался покинуть Новгород, хотя Мстислав уверял, что не претендует на правый берег Днепра. Только 3 года спустя Ярослав с дружиной явился в Киев. На предложенную братом границу по Днепру ему пришлось согласиться.[5]
Томаторкань стала большой страной. В Чернигове, Курске и Рязани жили северяне и вятичи. В степях же оставались прежние полукочевые племена, казары, касаки. Между Доном и Донцом торки, перемешанные с казарскими печенегами. Около Хопра и Верхнего Дона берендеи, которых арабы раньше знали у Терека как беренджеров, или венендеров, рядом с ними на Медведице бродники и в Приазовье остатки асаланов. Все эти степняки и кавказцы служили крепкой опорой против всех врагов князя.