Около 830 г. в украинские степи тем временем вошли новые кочевые племена – угры (венгры). Венгерский союз племен, возникший в Хазарском каганате, был этнически смешанным и состоял из угро-финнов и тюрков. В причерноморских степях венгры продержались недолго. В конце IX в. под натиском печенегов они перешли Карпаты и завоевали славянское государство Великую Моравию, постепенно став оседлым народом, причем, в отличие от булгар, венгры смешались с местным населением, но при этом создали в центре Европы своеобразный угро-финский языковой остров.
В украинских степях, теперь уже надолго, появился новый хозяин – прикочевавшие из степей к северу от Каспийского моря тюркские племена печенегов. К середине X в. кочевья восьми печенежских племен занимали пространство от Дона до Дуная, а на севере, на правом берегу Днепра, до Роси, на левом – до устья Сулы и низовья Ворсклы. Можно уверенно сказать, что именно печенеги погубили все предыдущие завоевания степной и лесостепной земледельческой колонизации. С 915 по 1036 г. Киевская Русь воевала с ними около 16-ти раз, но так и не смогла продвинуться на юг далее, чем на 100–150 км от Киева. На этих войнах с печенегами были приобретены основные навыки сопротивления набегам степняков, в первую очередь характерной для них тактике ведения боя. Последнюю, успешную, битву с печенегами летопись связывает с именем Ярослава Мудрого, датируя 1036 годом. Под стенами Киева печенеги потерпели столь сокрушительное поражение, что начали откочевывать за Дунай, где смешались с местным населением. Оставшимся на своих старых кочевьях через два десятилетия пришлось искать помощи у киевского князя и вместе с другими кочевыми племенами (узами и берендеями) стать своеобразным буфером между земледельческой зоной и степью.
В Северное Причерноморье после недолгого господства торков (узов) вступили новые хозяева – половцы. Этим словом на Руси называли тюркский этнос кипчаков, образовавших племенной союз под названием куманы ("куман" дословно обозначает "светло-желтый", отсюда славянское "половец", "половый"). Некоторые исследователи считают кипчаков тюркизированным сако-иранским этносом, во всяком случае антропологи квалифицируют половцев как чрезвычайно смешанную расу – от голубоглазых блондинов до типичных монголоидов.
С определением половецкого языка дело обстоит проще. Забегая наперед, можно сказать, что половцы быстро ассимилировали своих завоевателей – монголов, – и когда торговавшие в Крыму генуэзские и немецкие купцы начали составлять своеобразные разговорники, кипчакский оставался основным языком Степи. "Кодекс Куманикус" – сводная тетрадь из латинско-персидско-кипчакского словаря и перевод разных христианских текстов со средневерхненемецкого дает возможность с полной уверенностью утверждать, что этот язык принадлежал к одной группе (она и сейчас называется кипчакской) с современными казахским, татарским, башкирским, ногайским и еще некоторыми тюркскими языками. Таким образом, половцы в языковом плане несколько отличались от своих предшественников печенегов. Те, очевидно, принадлежали по языку к другой тюркской группе – огузской (современные турецкий, туркменский, азербайджанский языки). В украинской степи появился новый этнический, вначале весьма рыхлый массив. Он формировался по тем же законам, что и все остальные кочевые народы древности, как несколько столетий назад формировались древние этносы булгар, венгров и печенегов.
Одной из существенных закономерностей этого процесса является то, что народ, давший имя новому этническому образованию, вовсе не обязательно бывает в нем самым многочисленным, но он просто благодаря удачно сложившейся исторической обстановке и энергичному военачальнику выдвигается на ведущее место в формирующемся объединении. В данном случае это место заняли кипчаки. Они стали тем мощным ядром, вокруг которого объединились все разрозненные и разбросанные по западу Великой степи орды, а частично и остатки сохранившегося со времен хазар земледельческого населения.
В 1060 г. половцы предприняли первый набег на Русь, Черниговскую землю, но были отбиты родоначальником Ольговичей – Святославом Ярославичем. Но уже зимой следующего года они наголову разгромили под Переяславом князя Всеволода Ярославича – родоначальника Мономаховичей. В 1068 г. снова под Переяславом, на реке Альте, половцы разбили уже объединенное войско трех старших сыновей Ярослава Мудрого. С тех пор битвы с половцами на протяжении столетия (учитывая перерыв в XII в.) стали головной болью князей, а также излюбленной темой героического фольклора и литературы. В целом, к началу XIII в. половцы совершили 46 больших походов на Русь, причем 19 из них пришлось на Переяславщину, 16 – на Киевскую землю, 7 – на Чернигово-Северщину и 4 – на Рязанское княжество. О половецких наемниках разных князей можно и не говорить. Первым нанял половцев для борьбы со своим дядей Всеволодом будущий черниговский князь Олег Святославич уже в 1078 г. В дальнейшем этот князь-авантюрист, образно названный в "Слове о полку Игореве" Гориславичем, много раз водил половцев на Русь. Характерно, что на протяжении всего XII в. его потомки Ольговичи особенно охотно роднились с половцами (сам Олег был зятем половецкого хана) и постоянно призывали свою многочисленную родню к участию в междоусобицах. Галицкие и волынские князья охотно использовали половецкую кавалерию в войнах с венграми и поляками.
После тяжелых для Руси 90-х годов XI в. походы Владимира Мономаха (1103–1116 гг.), сопровождавшиеся массовым истреблением женщин и детей, превратились в настоящий геноцид половцев. Потеряв лучшие стойбища и огромное количество скота, половцы даже откочевали за Дон. Когда в 1120 г. сын Мономаха Ярополк маршем прошел к Дону через всю степь, то половцев так и не встретил. Мстислав Великий, последний киевский князь, имевший власть, близкую к самодержавной, вообще, по словам летописи, заставил половцев отойти за Волгу и Кубань. Впрочем, успех этот был эфемерным. За короткое время Русь-Украина была не в состоянии заселить и распахать огромное пространство. Воспользовавшись известной войной за Киев между Изяславом Мстиславичем и Юрием Долгоруким, половцы постепенно возвращаются и занимают старые территории. В XII в. летописцы и географы как на Руси, так и в Европе и на Востоке все степи от верховьев Дона до южного берега Крыма и от Иртыша до Дуная называют землей кипчаков, или Дешт-и-Кипчак – Половецкой степью.
В письменных источниках почти не сохранилось сведений о размерах кочевнических, в частности половецких, орд. Тем не менее, по отрывочным упоминаниям можно составить определенное представление о них. Обычно одна орда, как объединение родов и больших семей, насчитывала порядка 40 тыс. человек и при среднем соотношении количества воинов ко всему количеству населения 1:5 могла выставить 7–9 тыс. вооруженных всадников. К территории Украины непосредственно примыкали пять орд: Побужская (собственно куманы), Лукоморская (современная Херсонская, частично Запорожская обл. и степной Крым), Приднепровская, Донецкая (бассейн Северского Донца), Нижнедонская. Впрочем, точнее было бы их назвать половецкими региональными политическими объединениями. Всего же орд (т. е. крупных родовых объединений) в степи между Волгой и Дунаем кочевало 12–15. Численность орд составляла от 20 до 40 тыс. человек, причем преобладали 40-тысячные. Таким образом, общее население Половецкой степи составляло порядка 500–600 тыс. человек. Если учесть, что в среднем малая семья в пять человек, чтобы вести кочевое хозяйство, нуждалась в стаде, по поголовью соответствовавшем 25 лошадям (одну лошадь можно приравнять к 5 головам рогатого скота + 6 овцам), то нетрудно представить себе размеры передвигавшихся по степям соединенных кочевий. Не следует забывать и о степных богачах, владевших стадами, состоявшими из тысяч коней и десятков тысяч голов овец. Поэтому, несмотря на природные богатства, в украинских степях могло прокормиться небольшое количество кочевников-скотоводов. В Киевской Руси проживало в то время порядка 6 млн человек. Причем, несмотря на все катаклизмы, домонгольская Русь знала только два массовых голода – для средневековой Европы цифра более чем скромная. Тучные черноземы самой природой были созданы для плуга, а не выпаса овец и лошадей. Но к моменту битвы на Калке половцы все еще предпочитали существовать за счет развития скотоводства и торговли с портовыми городами Крыма, где начали обосновываться венецианцы и генуэзцы (половцы поняли, что с городами выгоднее не воевать, а торговать).