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