Почти в одно время с Ростиславом против Ярославичей поднялся другой племянник, впрочем двоюродный. Это был полоцкий князь Всеслав, сын Брячислава (умершего в 1044 г.). Своим предприимчивым и беспокойным характером он не уступал Ростиславу. Летопись изображает его князем хитрым и жестоким. У него от природы была на голове какая-то язвина, вследствие чего он носил повязку, и суеверные люди приписывали этой повязке особое, волшебное значение. Всеслав, по всей вероятности, питал неудовольствие за то, что его ограничивали одною Полоцкой областью и не давали ему части в других русских землях. Подобно отцу своему, он обнаружил притязания на Новгородский край или по крайней мере на ближние новгородские волости. Сначала он пытался осаждать Псков, но без успеха; затем явился с войском под самым Новгородом, ворвался в него и сжег часть города; причем ограбил храм Святой Софии, сняв самые колокола и паникадила. Тогда Ярославичи соединенными силами отправились воевать Полоцкую землю. Они взяли город Минск и, со свойственною тому времени жестокостью, избили мужское население, а жен и детей раздали в рабство своим дружинникам. Всеслав встретил дядей недалеко от этого города на берегах речки Немизы. Дело происходило в марте месяце, и земля была еще покрыта глубоким снегом. После упорной битвы Ярославичи победили; но, очевидно, борьба с таким противником оказалась нелегкой, так как они предпочли прибегнуть к вероломству. Князья съехались для переговоров где-то около Смоленска и расположились лагерем на противоположных берегах Днепра. Ярославичи пригласили Всеслава переехать на их сторону и поцеловали крест, то есть присягнули в его безопасности. Но едва Изяслав ввел его в свой шатер, как полоцкого князя схватили, отвезли в Киев и засадили в поруб вместе с двумя его сыновьями16
.Такое вероломство, по словам летописца, не замедлило вызвать Божье наказание на князей-клятвопреступников. Русскую землю посетили новые враги-иноплеменники. То были половцы, народ одного корня с печенегами, но еще более дикий и многочисленный.
После известного поражения печенегов под самым Киевом в 1036 году наша летопись уже не упоминает об их нашествиях на Русскую землю. Упорная, победоносная борьба с ними Владимира и Ярослава, очевидно, ослабила их силу; окончательно их сломили собственные междоусобия и другие кочевники, надвигавшиеся с востока. В IX веке, как известно, печенегов оттеснили из-за Дона их единоплеменники узы в союзе с хазарскими каганами. Когда печенеги рассеялись в Черноморских степях по обеим сторонам Днепра, узы заняли их кочевья в степях Задонских. Не все печенеги ушли из прежних своих степей; часть их осталась между узами, от которых, по словам Константина Багрянородного, они отличались более коротким платьем, достигавшим только до колен и не имевшим рукавов. В первой половине X века, по известию того же Константина, пустынное пространство в пять дней езды отделяло печенегов от узов. Но последние недолго оставались в покое на новых местах. В свою очередь, теснимые другими кочевниками, они перешли на западную сторону Дона и стали подвигать свои кочевья к степям Днепровским, где снова столкнулись с печенегами. Подобно печенегам, узы были турко-татарский народ, делившийся на разные орды под управлением своих родовых старейшин, или ханов. Русские князья в борьбе с печенегами пользовались иногда их враждою с узами. Из последних, так же как из первых, они при случае нанимали вспомогательную конницу для войны с соседями. Мы видели, что уже Владимир Великий в походе против камских болгар имел у себя конных торков. Этим именем русская летопись называет узов.
Печенеги еще храбро держались против узов. Но в последние годы Ярославова княжения между печенежскими ордами возникли жестокие междоусобия. Поводом к ним послужила вражда самого сильного из печенежских ханов Тураха против Кегена, который из простых людей возвысился в число главных старейшин, благодаря своим подвигам в войнах с узами. Теснимый соперником, Кеген убежал с частью печенегов за Дунай и отдался под покровительство императора Константина Мономаха с обязанностью защищать греческие пределы от набегов собственных соплеменников. Тогда узы окончательно взяли верх над печенегами, которые оставались в степях между Днепром и Дунаем, что побудило последних к новым переходам за Дунай, где они получали от византийского правительства земли для поселения преимущественно в тех местах Болгарии, которые запустели после истребительных войн Василия II Болгаробойцы.