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