В тот же период на историческую сцену Восточной Европы вышли куманы. К середине XI в. они захватили почти всю территорию современного Казахстана, пересекли нижнее течение Волги и появились в южнорусских степях. Голубоглазых, светловолосых куманов на Руси стали называть половцами (от слова «полова», которое означает рубленую солому, имеющую матово-желтый цвет). У половцев был давний заклятый враг — печенеги. «Степная вендетта», длившаяся века, в XI в. особенно ожесточилась из-за вероисповеданий. Как мы знаем, печенеги приняли ислам, половцы же сохраняли языческие верования своих предков.
После смерти Ярослава Мудрого князь Всеволод пытался установить контакты с половцами, но безуспешно. Постоянные стычки русских и половцев завершились тем, что а сентябре 1068 г. половцы двинулись в большой поход на Русскую землю. Трое Ярославичей: Изяслав, Святослав и Всеволод — встретили кочевников на реке Альте. Кавалерийский бой оказался для русских неудачным. Как сказал поэт:
С рассветом на половцев князь
Там выехал, грозен и злобен.
Свой меч двоеручный высоко подъяв,
Святому Георгью подобен;
Но к ночи, руками за гриву держась,
Конем увлекаемый с бою,
Уж по полю мчался израненный князь,
С закинутой навзничь главою.
Ярославичи потерпели поражение. Изяслав бежал в Киев, где киевляне потребовали у него оружие и коней, чтобы вновь сразиться с половцами. Но князь не решился дать народу оружие: западник Изяслав хорошо знал свою непопулярность. Киев возмутился, и великий князь, забрав сына Мстислава, бежал в Польшу. Его дальнейшие странствия сами по себе очень интересны, но сейчас для нас важны исход половецкого нашествия и события в Киеве.
1 ноября того же 1068 г. черниговский князь Святослав Ярославич, имея всего 3 тысячи русских ратников, наголову разбил 12 тысяч половцев в битве на реке Снови. Оказалось, что половцы удачливы в коротких набегах и стычках конных отрядов, но борьба с русскими городами и русской пехотой им была не под силу. Поэтому опасности для существования Руси половцы не представляли.
По странной иронии судьбы, половцы оказались спасителями Византии, так как она, теснимая печенегами и в Европе, и в Азии, призвала куманов-половцев на помощь. Ханы Боняк и Шарукан привели на Балканский полуостров конные рати куманов. К 1091 г. с печенегами на Балканах было покончено. Прижатые половцами и византийцами к морю у мыса Лебурн, печенеги были частью уничтожены, частью захвачены в плен. Союзники по-разному распорядились судьбой пленников. Греки своих перебили, а половцы присоединили к собственному войску. Из остатков печенегов сложился доныне существующий народ — гагаузы.
В годы, полные войн с половцами и княжеских усобиц, проявил себя Всеслав, князь Полоцкий, внук Изяслава Владимировича, сына Владимира Крестителя. Судьба и деятельность Всеслава Полоцкого необычайно интересны.
Полоцк сохранил память о разгроме города Владимиром в 980 г., когда будущий великий князь убил князя Рогволода и его сыновей и надругался над дочерью Рогволода Рогнедой. По расправе с княжеской семьей можно представить, как вели себя новгородцы и наемные варяги в захваченном городе. Когда же на княжеском столе Полоцка оказался потомок Рогнеды Всеслав, полочане активно поддержали своего князя в войне с Псковом, а затем и с Новгородом.