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