В продолжение всего XII в. шла упорная борьба русской земли с половцами, укреплялись и огораживались её пределы; иногда русские предпринимали походы на Дон, в центр половецких кочевьев, как например в 1110 г. (Владимир Мономах) и 1185 г. (кн. Игорь). Результатами этой борьбы было оттеснение Руси кочевниками от берегов Черного моря, из Крыма и Тамани, так что после 1094 г. русские источники уже не говорят о Тмутараканьском княжестве. Более устойчивыми оказались славянские города, находившиеся в северо-западной части побережья Черного моря, в устьях больших рек. Так, сохранялись «болгарские» города по Дунаю, куда Владимир Мономах ставил своих посадников. Затем в устье Днестра известны Белгород, Чернь, Аскей, Торь, а в устье Днепра — Олешье, которым в 1084 г. овладел кн. Давид Игоревич, и которое находилось также в зависимости от галицкого князя Ярослава Осьмомысла. Что касается степной полосы, отделявшей побережье от оседлых центров, то отсюда население уходило под прикрытие естественных и искусственных укреплений и лишь редкими оазисами попадалось в защищенных местах по берегам рек Донецкого бассейна. Господствующее положение в степях заняли кочевники да близкая к ним по образу жизни и привычкам, хотя и исповедовавшая христианскую религию, полуславянская-полутюркская помесь «бродники» (см. «Россия», т. II, стр. 122 и т. VII, стр. 65 и 71). Известие о бродниках в нашей летописи появилось с первой половины XII в. По-видимому им принадлежал основанный выходцами из Галицкого княжества г. Берлад на притоке Серета Берладе.
Отливу славянского населения из степей обязано было появление нового юго-западного центра древней Руси, после того как историческая роль Киева, с постепенным прекращением византийской торговли и перенесением главной части киевского центра на северо-восток, во Владимир на Клязьме, была сыграна. Так выросла земля белохорватов или Червонная Русь, занимавшая пространство по верхнему течению Днестра и Прута, т. е. нынешнюю Галицию, часть Подольской губернии и северную часть (Хотинский уезд) Бессарабской губернии. Сила этого княжества основывалась на соперничестве трех соседних государств — Руси, Венгрии и Польши, а частью обязана была ряду даровитых князей. Наиболее популярный из них Ярослав Осьмомысл так воспет в знаменитом «Слове о полку Игореве»: «высоко сидишь ты на своем златокованом престоле; ты подпер Карпатские горы своими железными полками и загородил дорогу королю венгерскому, затворил ворота к Дунаю; ты один судишь и рядишь до самого Дуная. Как гроза разносится твое имя по всем землям и открывает вход в Киев; с отцовского золотого престола стреляешь ты султанов в далеких землях». Значительно силы достигло княжество при Романе Мстиславиче Волынском, который соединил Волынское княжество с Галицким. Этот князе успешно воевал с половцами и с новым растущим соседом — Литвой. Еще большего могущества достигло Галицкое княжество, снова отделившееся от Волынского при Данииле Романовиче благодаря сильному наплыву русского населения, устрашенного появлением новых кочевников — татар.
Первое столкновение с татарами, окончившееся поражением русских, произошло в пределах области на р. Калке (ныне Калемиус Екатеринославской губернии). Затем между 1239-41 гг. татары прошли грозной, всесокрушающей силой южной Русью, по пути разорив Киев, Волынь, Галич и др. города, и достигли Венгрии, откуда, потерпев неудачу, возвратились в южно-русские степи, где и утвердились надолго, подчинив себе всю европейскую Украину. Прежние властители степи — половцы частью ушли в русские пределы и в Венгрию, частью смешались с татарами, бродники же на время сумели сохраните свою независимость, действуя то в союзе с татарами, то отдельно. Главным центром своего местопребывания татары избрали низовья Волги, где и основали Золотую Орду. В пределах Новороссийской области наибольшее число оседлых стоянок и кочевьев приходилось на Донскую область и восточную часть Екатеринославской губернии. В Донской области, где их жилища особенно умножились после мора 1348 г., выгнавшего их из волжских стоянок, они распространились по всему Дону, Донцу, Медведице и частью Хопру. О пребывании их здесь свидетельствуют развалины кирпичных мечетей с внутренними стенами из цветных камней и остатки жилищ близ Глазуновской станицы в Усть-Медведицком округе, по р. Иловле, Чиру, Сускану, Куртлаку, Царице и Салу (1-го и 2-го Донских округов). По направлению к западу и особенно за Днепром татарские кочевья уже заметно редели, почему здесь больше сохранилось остатков прежних кочевых народов, особенно половцев. Вследствие отдаленности от татарского центра бродившие здесь орды чувствовали себя самостоятельней и даже делали попытки обособления. Так, в 1271 г. ненадолго образовалось ногайское ханство из едисанских и джамбулакских татар. Благодаря той же обособленности некоторое время могло держаться и славянское население по городам, уцелевшим после татарского погрома. В известном списке городов, составленном не позже XIV в., обозначены русские города Романов Торг (ныне Роман) на р. Пруте и Хотин на Днестре. Что касается прибрежных поселений, то они, утратив связи со славянскими центрами, быстро пустели и замирали. Как ясно из карт венецианских и генуэзских купцов, посещавших свои черноморские фактории, до конца XIV в. в северо-западной части черноморского побережья не было никаких поселений, в конце же XIV в. татары основали на месте нынешней Одессы поселение Гаджибей и, может быть, в это время был основан г. Очаков.