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