О Тмутаракани в памяти русских вскоре не осталось ничего, кроме смутных воспоминаний о чем-то, находящемся очень далеко. Даже местонахождение Тмутаракани полностью забыли, так что в XVI веке московские летописцы считали Тмутараканью город Астрахань[257].

Вторжения половцев, первое из которых произошло еще в 1061 году, три десятилетия спустя приняли характер массового вторжения. В 1090-х годах половцы почти непрерывно вторгаются на Русь. Занятые усобицами русские князья не только не способны были отбить половецкий натиск, но нередко и сами приглашали половцев пограбить владения своих соперников. У половцев выдвинулись крупные полководцы Тугоркан (в русских былинах его называли Тугарин Змеевич) и Боняк Шелудивый. В 1093 году половцы разгромили дружины русских князей под Треполем (на реке Стугне), а три года спустя разграбили окрестности Киева и сожгли Печерский монастырь.

Степная граница Руси теперь проходила неустойчивой ломаной линией от Межибожья к нижнему течению реки Роси, откуда круто поворачивала на северо-восток к верховьям рек Сулы, Пела, Воркслы, Северского Донца, Дона и Прони.

Русские князья под давлением половецкой опасности начали сплачиваться. Уже в 1096 году Владимир Мономах нанес поражение половцам на реке Трубеж. Под руководством Владимира Мономаха объединенные русские дружины совершили ряд удачных походов против половцев в 1103, 1107, 1111 годах. В ходе последнего похода половцы потерпели особенно тяжелое поражение на реке Сальнице. Мономаху удалось приостановить половецкие вторжения, благодаря чему авторитет этого князя поднялся очень высоко. В 1113 году он стал великим князем Руси. Владимир Мономах стал последним князем, правившим всей Русью. Парадоксальным образом, именно в результате побед Мономаха и ослабления половецкой угрозы удельные князья теперь не нуждались в единой центральной власти великого князя, и поэтому, по словам летописца, «раздрася земля Русская». Половецкие набеги на русские земли продолжались, но уже не столь масштабные, как при Тугоркане и Боняке. Русские же князья по-прежнему «приводили» половцев на земли своих соперников.

Из-за половецких вторжений значительно было оттеснено на лесной север славянское население с Приднестровья и Побужья (среднего и нижнего течений реки Южный Буг), где когда-то проживали уличи и тиверцы. Но в XII веке их плодородные земли стали напоминать пустынную степь. На среднем Днепре «Половецкое поле» подходило уже к самому Киеву. На Дону славянское население осталось лишь у самых истоков реки. В степях на нижнем Дону еще существовали небольшие городки, где проживали славяне, ясы (аланы), остатки хазар, исповедующие православие. Летописец описал городок Шарукань, жители которого вышли встречать русские дружины православной духовной процессией.