На картах з початку XVII ст. і практично до середини XVIII-го на місці сучасного Херсона розташовувалося місто Bilehowisce (Біліховичи, Білховичи). Незважаючи на те, що Біліховичи на картах позначалося до середини 18 століття, швидше за все, місто до приходу фельдмаршала Мініха в гирло Дніпра, було вже у великому занепаді[1]. У книзі Себастьяна де Учедо «Покажчик відомого світу» 1672 року, в списку Європейської Тартарії, позначено міста: Очаків, Білховичи, Качибей, Вінарадна, Крапезаді, Андріїв[2]. У книзі Германа Моля «Система Географії» 1701 року, в списку Очаківської Тартарії, позначено міста: Очаків, Білховичи, Качибей, Винарадна Круча[3].
Рум'янцев з 1736 перебував в армії під керівництвом Мініха, брав участь у взятті Очакова, закріпив усі пости української лінії до Києва. 1738 року призначений правителем Малоросії[5]
Російсько-турецька війна, яка тривала виснажливих п'ять років, закінчилась Кучук-Кайнажирським миром, підписанним 1774 року. Згідно з цією угодою, херсонські степи були визнані за Росією та увійшли до складу новоствореного Новоросійського Генерал-Губернаторства. Розпочалась активна діяльність Уряду щодо заселення краю та будівлі міст.
11 червня1778 року імператриця Катериною II видала наказ на ім'я князя Потьомкіна про необхідність знайти у гирлі Дніпра місце, зручне для будівництва міста з фортецею та верфі. Таким місцем і стало напівзруйноване польове укріплення Олександр-Шанц.
8 вересня 1778 року розпочались фортифікаційні роботи. Одночасно з будівництвом фортеці та цивільних будівель розпочалось і прискорене будівництво верфі. Відповідно до наказу Катерини II, місто було названо Херсоном.
Оскільки фортеця знаходилась у безпосередній близькості до володінь татар, її охорону доручили козакам, які перетворили Олександр-Шанц на центр однієї з територіальних дільниць Запоріжжя — Перевізької (Інгульської) паланки. Спочатку тут розміщувались 219 козаків із полковим старшиною. До обов'язків паланки входив контроль над рибними промислами і зимовниками в гирлі Дніпра, частина яких знаходилась в межах сучасного Херсона: на острові Кошовому (нині о. Карантинний), на місці взуттєвої фабрики, в районі Забалки, селищ Антонівка, Кіндійка, Зеленівка[джерело?].
