9 января 1737 года была наконец заключена австро-российская конвенция о совместной войне против османов. Несмотря на то, что о территориальных претензиях обеих сторон в документе не говорилось, в ходе переговоров Австрия фактически признала необходимость присоединения Крыма к России.

Кампании 1737–1739 годов Россия вела уже совместно со своим западным союзником. Тем самым был создан исторический прецедент, повторившийся во вторую русско-турецкую войну Екатерины II, когда русские и австрийцы снова помогали друг другу в борьбе с общим врагом.

И если в «екатерининскую» эпоху военные потенциалы России и Османской империи были сопоставимы, то начиная войну 1735–1739 годов, правительство царицы Анны сильно рисковало. Не начни Австрия боевые действия, Турции не пришлось делить свои силы между Причерноморьем и Западными Балканами. А значит, и результат войны мог бы быть совсем иным.

Это объясняет, почему Петербург поспешил вступить в мирные переговоры с Портой, как только Вена заявила о выходе из войны.

В сентябре 1739 года между Россией и Османской империей был заключён Белградский мирный договор. По нему среди прочего Петербург получал контроль над участком Правобережья Днепра в районе поселения Новый Миргород (ныне город Новомиргород Кировоградской области).

В правление двоюродной сестры царицы Анны – Елизаветы Петровны, через полтора десятилетия после мира в Белграде у Нового Миргорода была создана провинция Новая Сербия. Для её прикрытия от набегов степняков построили крепость Святой Елизаветы – впоследствии город Елисаветград. Именно ему и предстояло стать первым административным центром Новороссийской губернии при её учреждении императрицей Екатериной II в 1764 году.

Но влияние Анны Иоанновны на судьбу Новороссии проявлялось не только в формировании территориальной основы, но и в организации колонизации региона.

В 1730 году в Полтавско-Екатеринославском пограничье и в южной части Харьковского региона (между Днепром и Северским Донцом) стартовало строительство Украинской укреплённой линии. Ее общая протяженность составляла около 300 километров. В целях обустройства укрепрайона и службы здесь из Белгородской и Воронежской губерний переселялись русские однодворцы (военно-служилое население, занимавшееся охраной границы).

Проект укреплённой линии предусматривал возведение 16-ти крепостей, соединённых непрерывным валом и рвом.

Первая из заложенных крепостей получила название Ивановская – в честь отца царицы Ивана V. Позднее, в честь её матери Парасковьи Фёдоровны была заложена Парасковейская крепость (ныне – село Парасковия Харьковской области). В честь первых царей из династии Романовых были названы Михайловская и Алексеевская крепости (ныне – сёла Михайловка и Алексеевка Первомайского района Харьковской области). Именем небесного покровителя Петра I была названа Петровская крепость (ныне – село Петровское Харьковской области).

Строительные работы в основном проводились силами казаков малороссийских и слободских полков, а также крестьян, принадлежавших казацкой старшине, духовенству и помещикам.

Впоследствии за счёт активной миграции малороссов в поселения на укреплённой линии здесь сформировалось смешанное русско-украинское население.

Практику русско-украинской колонизации региона восприняла Екатерина II, когда повелела раздавать земли в бывшей Новой Сербии русским дворянам и сняла запрет на переселение туда выходцев из Малороссии. Новороссийский наместник Григорий Потёмкин добился облегчения переходов в Причерноморье крестьян из губерний Великороссии и выходцев с Правобережной Украины.