В 1036 году печенеги-мусульмане совершили набег на Киев, но с большими потерями были отбиты. В 1046 году большая часть печенегов ушла из Северного Причерноморья в набег на Византию. В 1051 году они подходили к Константинополю, но не смогли его взять и отошли на Балканы.
Остатки печенегов уже не могли играть ведущей роли в степи. На смену им пришел новый племенной союз – половцы.
В Х веке от государства кимаков, находившегося на западных склонах Алтая, откололось племя кыпчаков, которое какое-то время кочевало между Алтаем и Каспийским морем, враждовало с печенегами и торками и, наконец, вышло в Причерноморские степи, где стало известно под именем «куманов» или «половцев». Это были тюркоязычные европеоиды, светловолосые и светлоглазые. Религией их было почитание Тенгри – Синего неба. Как писал арабский географ ХIV века, «кыпчаки отличаются от других тюрков своей религиозностью, храбростью, быстротой движения, красотой фигуры, правильностью черт лица и благородством».
В 1055 году 300–400 тысяч половцев вышли к границам русских княжеств и, как всегда бывает в таких случаях, попробовали своих новых соседей на прочность.
Русские отбили несколько половецких набегов. Некоторые князья, воюя друг с другом, стали даже приглашать половцев к себе в союзники, призывать их на русскую землю. Однако киевский князь Владимир Мономах сам пошел в поход в степь на половцев и в 1103, 1111 и 1116 годах погромил их стойбища. У половцев не было крепостей, как у русских, их семьи, жены и дети передвигались на повозках, запряженных волами, и не могли убежать от русской конницы.
В конце концов обе стороны осознали бесполезность войны. Половцы поняли, что им не победить русских, которых к тому времени было более 5 миллионов. Постепенно они стали втягиваться в тесные отношения с русскими, стали союзниками черниговских и галицких князей (у киевских князей союзниками были враждебные половцам торки). Считается, что половцы, кочевавшие западнее Дона – Западный половецкий союз, – вместе с русскими составляли одно полицентрическое государство, южные земли которого лежали между Доном и Карпатами.
Задонские половцы, кочевавшие по левому берегу Дона и в его верховьях, назывались русскими князьями «дикими половцами». Они в 1117 году вытеснили русских из Белой Вежи и разбили русских союзников – торков.
Однако «дикие» половцы не решались открыто враждовать с русскими. Они предпочитали иметь союзнические отношения с суздальскими князьями. Кроме того, они опасались оставшихся в пойме Дона славян, получивших название «бродники». Эти «бродники» продолжали жить на Дону даже после оставления Белой Вежи и в случае войны могли ударить половцам в тыл.