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