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