В 1638 году была сооружена Кременчугская крепость, план которой разработал французский военный инженер Гийом Левассер де Боплан.

В 1667 году Кременчуг перешёл под управление Миргородского полка.

В 1764 году Кременчуг вошёл в новообразованную Новороссийскую губернию и до 1783 года был её губернским городом.

Утверждённый в 1764 году «План о раздаче в Новороссийской губернии казенных земель к их заселению» торжественно объявлял, что поселенцы независимо от того, откуда они пришли, будут пользоваться всеми правами «старинных российских подданных». Тем не менее уже тогда формировались условия для преимущественно великоросской (русской) колонизации Новороссии.

В 1770 году была построена так называемая Днепровская линия. Её появление стало результатом побед в турецкой войне (взятие Азова и Таганрога).

Днепровская линия должна была отделять всю Новороссийскую губернию вместе с запорожскими землями от владений крымцев. Она протянулась от Днепра и шла к Азовскому морю, проходя по рекам Берде и Конским Водам, и пересекала всю крымскую степь. Последняя её крепость, Святого Петра, находилась у самого моря, рядом с современным Бердянском. Всего в этой линии было восемь крепостей.

КСТАТИ

10 мая 1770 года императрица Екатерина II утвердила двенадцать «докладных пунктов» Военной коллегии и кандидатуру генерал-поручика М.А. Деденева на должность главного командира Днепровской линии. На вопрос о том, как должны именоваться линия с редутами и семь крепостей, императрица вынесла резолюцию, что крепости должны называться: Кирилловская, Александровская, Петровская, Никитинская, Захарьевская, Григорьевская, Алексеевская. Они должны были отстоять друг от друга на тридцать вёрст.

Есть версия, что крепости Днепровской линии были названы императрицей именами членов Совета, которые имели непосредственное отношение к выработке решений по созданию линии.

После присоединения Крымского ханства к Российской империи южные границы бывшего ханства автоматически стали границами России. Днепровская линия, проходившая по старой границе, оказалась от новой границы далеко внутри государства. 10 февраля 1784 года императрица Екатерина II своим указом предписала в связи с изменившимися границами государства устроить новые пограничные укрепления и упразднить старые, которые оказались «внутри пределов государства».

В 1770 году был основан Александровск (будущий город Запорожье). Город возник там, где заканчивались многочисленные Днепровские пороги. Ещё до появления Запорожской Сечи на острове Хортица (самом крупном на Днепре) существовал скифский городок. Остров упоминается в древнерусских летописях как место битв и сбора князей, здесь, возможно, находилась «столица» летописных бродников – Протолча, торгово-ремесленное поселение по имени известного брода. Александровск стал важнейшим транспортным узлом Новороссии.

Освоение Новороссии происходило под руководством князя Григория Александровича Потёмкина. Он известен тем, что в 1776 году построил новый центр Новороссии – Екатеринослав, который задумывался в качестве третьей столицы России и главного города Новороссии. Именно в Екатеринослав из Кременчуга и была перенесена столица Новороссии.