В середине XI в. четыре округа (орды) печенегов, кочевавшие между Днестром и Днепром, распались, и самой крупной административной единицей стала считаться «часть» или «колено», как называл их Константин Багрянородный. По сообщению другого византийца — Кедрина, писавшего в XI в., 13 печенежских колен обитали на берегу Черного моря, между Днепром и Дунаем. Над всеми ними стоял верховный военачальник — Тирах, слабый и безынициативный человек, не пользовавшийся популярностью у своих единоплеменников. На борьбу с Русью у печенегов уже не было сил, отдельные приднепровские роды — аилы отражали натиск новых кочевников гузов и половцев. Большинство же отступило к границам Византии. Там они были частично уничтожены византийскими войсками. Оставшиеся роды были поселены в византийском пограничье — в степях между Балканами и Дунаем.
В конце XI в. печенеги, немного окрепнув, вновь решили «попытать счастья» в Византии. Они широкой волной хлынули в империю, разрушая небольшие городки, вытаптывая пашни. Об этом сохранился подробный рассказ византийской писательницы и царевны Анны Комниной — дочери царствовавшего тогда Алексея Комнина.
Для борьбы с печенегами император привлек половцев, которые помогли ему одержать решающую победу. В ночь после битвы окруженные со всех сторон печенеги были вырезаны византийцами. Погибло более 30 тыс. печенегов. Однако и после этого побоища печенеги вплоть до монголо-татарского нашествия упоминаются в источниках: особенно часто в русской летописи, поскольку вместе с некоторыми другими кочевническими этническими группировками и ордами, они, получив во владение Поросье, стали вассалами Руси.
Печенеги в период своего столетнего господства в Причерноморских степях так и не перешли ко второй стадии кочевания.
Наиболее выразительный пример перерастания первой формы кочевания во вторую — половцы, впервые зафиксированные в восточноевропейских степях русской летописью под 1055 г.
Первая половина XI в. знаменуется появлением в Причерноморье еще одного народа — гузов или, как их называет русский летописец, торков. Орды торков представляли собой северную ветвь мощного Сельджукского союза тюркоязычных племен. Северные гузы всеми силами пытались пробиться к границам Византии. Несмотря на явное их желание избежать столкновения с Русью, киевские князья, сыновья Ярослава Мудрого, возглавили большой поход против новых врагов. Торки, только услышав о приближении русских войск, испугались и поспешно отступили к границам Византии. Немногочисленные оставшиеся в степях отряды печенегов и торков не смогли противостоять идущим с востока ордам половцев, захватившим почти пустые пространства в бассейне Дона и в Приазовье.
В IX—X вв. половцы (кипчаки, как именовали их восточные авторы) кочевали в степях Прииртышья и Восточного Казахстана. В начале XI в. они появились в Поволжье, а в середине XI в. подкочевали уже к границам Руси. С конца 50-х годов XI в. летопись пестрит записями о грабительских походах половцев на русские пограничные княжества. Половцы не ограничивались грабежом русских окраин. Они уходили из восточноевропейских степей далеко на юго-запад: в Болгарию, Венгрию, Византию. Особенно прославились в походах XI в. два половецких военачальника — ханы Боняк и Тугоркан. Из византийских походов половцы привозили огромные богатства, получаемые в виде откупов, а чаще — в результате обычных грабежей городов и населения степей. Уже тогда они стали активными участниками русских междоусобиц, выступая на стороне то одного, то другого русского князя. Неоднократно воевали они на стороне русских в борьбе с соседними государствами — Венгрией, Польшей и др. Совместные походы были так выгодны половцам, что даже рьяный враг Руси хан Боняк соглашался иногда на военный союз с русскими князьями. Так, в 1097 г. он воевал вместе с князем Давыдом против Галицкой земли, на стороне которой были венгерские отряды.
В 1095 г. Тугоркан и Боняк последний раз ходили «на греки». На этот раз они шли на Византию с претендентом на императорский престол Романом Диогеном. Половцы были наголову разбиты, а Роман Диоген схвачен и ослеплен. Вернувшись в степи, половцы сделали попытку организовать большой поход на русские княжества, но и здесь потерпели поражение, причем в бою был убит Тугоркан.
В этот период половцы находились на первой стадии кочевания. Постоянные их передвижения по степи делали половцев практически неуловимыми. В течение всего XI в. русским не удалось организовать ни одного похода в глубь степи. Однако к концу XI в. жизнь в степях несколько стабилизировалась. Можно уверенно говорить о формировании в то время нескольких рыхлых объединений — орд, владевших определенными территориями, разделенными внутри на более или менее устойчивые кочевья с определенными стойбищами и путями перекочевок. Во главе одного из них — Приднепровского стояли Боняк и Тугоркан. Ордами на Нижнем Днепре, в так называемом Лукоморье, правил Урусоба, а в Подонье утвердился у власти род Шарукана.