Сумна перспектива ув’язнення на Соловках чи в Сибіру, конфіскації майна, покріпачення та здирств оминула більшість із запорозьких старшин. Ще 1777 року колишнім козацьким старшинам, котрі, як говорив Потьомкін, «у злочинах кошового та його спільників участі не брали», надали військові чини та дворянство. Цієї милості удостоїлись запорозький військовий осавул Сидір Білий, який став предводителем херсонського дворянства, та військовий писар Антін Головатий, призначений на посаду капітана-справника міста Новомосковська (начальник земської поліції). Згодом обидва вони отримали чини секунд-майорів, патенти на дворянство і завели поміщицькі господарства. З цими постатями пов’язане народження наступника Війська Запорозького — Чорноморського козацького війська. Доля Петра Калнишевського їх оминула лише тому, що вони напередодні і під час руйнування Січі перебували в Петербурзі із клопотанням для запорожців царських «милостей». Не знаючи, що генерал Текелія вже докінчив свою справу із Січчю, Головатий був на прийомі у царициного фаворита Григорія Потьомкіна і пропонував йому проект реформування Запорожжя за зразком Війська Донського. Вислухавши козацького старшину, Потьомкін мовив: «Браво!» — і жбурнув геть подані ним папери. А коли цей вельможа, граючись, з удаваним сумом сказав, що «Січ пропала», то Головатий з ледь прихованою злістю відповів: «Пропали ж і ви, ваша світлосте!» Потьомкін вперіщив у нього гнівний погляд, у якому вже замаячили Соловки, та Головатий дотепно повернув це на жарт, нагадавши князеві, що той записаний козаком до Кущівського куреня, отже, якщо «Січ пропала», то пропало і його козакування. Оцінивши дотеп запорожця, Потьомкін пом’якшив свій погляд і бовкнув: «Ти бреши, та не забрешися!»
Перед початком нової війни з Туреччиною Катерина II вирішила оглянути колишні землі запорозького козацтва та завойовані у турків причорноморські степи, де Потьомкін зводив губернські міста і поміщицькі села. З липня 1787 р. у Кременчуку колишні запорозькі старшини постали перед ясними царициними очима й подали їй клопотання про відновлення Війська Запорозького. Його автор, Антін Головатий, писав: «Це вже не буде Січчю, але особливе військо із колишніх запорожців, вони будуть мати свою осілість і порядок служби, гідний часові та обставинам». Тобто йшлося не про відновлення Війська Запорозького, а про створення нового козацького витвору, який хоч і мав спиратися на військові традиції запорожців, але зорганізовувався на кшталт Війська Донського. Всупереч січовим традиціям, козаки нового війська мали поодружуватися. Катерина II наголошувала Потьомкіну: «Щоб з вашого боку було вжито запобіжних заходів, аби зі згаданих колишніх запорожців не було заведено товариство неодружених людей ще й на їхньому старому підґрунті». Потьомкін наказав козакам негайно шукати наречених, і кожному, хто одружився, надсилав подарунок. Вважалося, що одружені козаки більше слухатимуть начальство й не тікатимуть до задунайців. Годі й говорити, що то були формальні реверанси задля вимолення прощі. Запорозькі звичаї та традиції передавали новим поколінням козацтва попри офіціозні декларації.
Краснодарський історик Борис Фролов днем народження Чорноморського козацького війська вважає 20 серпня 1787 року, коли Потьомкін видав отаке розпорядження: «Щоби мати у намісництві Катеринославському воєнні команди волонтерів, доручив я секунд-майорам Сидору Білому та Антону Головатому зібрати охочих, і кінних та піших для човнів з тих, хто поселився в цьому намісництві й служив в колишній Запорозькій Січі, козаків». Однак до створення справжнього козацького війська справа тоді ще не дійшла, адже у Потьомкіна все ще йшлося про «команду волонтерів». Тож і охочих йти у «волонтери» було мало. Тоді Потьомкін дозволив набирати у козаки не лише колишніх запорожців, але й будь-яких вільних людей, навіть бурлаків бездомних, аби вони тільки не були дезертирами чи не скоїли яких злочинів.
До створюваного війська приєднався Харько[14] Чепіга зі своєю півсотнею «волонтерів», набраних з «вільних людей». Йому Потьомкін пожалував полковницький пернач і дозволив вербувати у козаки. Колишній запорозький старшина — полковник Протовчанської паланки, а тепер — капітан російської армії, Чепіга також удостоївся царициних милостей. Вона ж, будучи в Кременчуку під час своєї помпезної подорожі до Криму, частувала його зі своїх рук виноградом і дарувала йому оздоблену діамантами шаблю. Цей козацький достойник увійшов до трійці батьків-засновників чорноморського козацтва, відзначившись ще й тим, що прибув до Васильківського Коша зі справжніми запорозькими клейнодами — знаменом Протовчанської палатки, перначами полковника і військового табунщика, які він урятував від конфіскації 1775 року.
27 лютого 1788 р. «вірні» козаки урочисто зустріли надіслані царицею військові клейноди — велике біле військове знамено, 7 малих знамен для куренів, булаву для кошового отамана та полковницькі перначі. Здавалося, що царський уряд, вже пошкодував через своє поквапливе рішення знищити Січ і зважився відновити козацький лад Запорожжя. Підбадьорені цим козаки стали повертатися з-за Дунаю до російських володінь. Однак кількість «вірних» козаків наприкінці 1787 р. ледь перевищувала 600 осіб. Зваживши на умовляння Білого і Головатого, Потьомкін оголосив, що колишні запорожці, котрі приведуть до війська охочих та забезпечать їх військовим обладунком, отримають офіцерські чини та дворянство. І от тоді чисельний склад почав зростати; вже у серпні 1788 р. лише команда Чепіги нараховувала 894 козаки. Поволі виокремлювалися назва і статус нового козацького війська. У січні 1788 р. його називали то «Кіш вірного Війська Запорозького», то «Козаками вірного Запорозького Коша», а в листопаді Потьомкін використав наймення «чорноморські козаки». У грудні остаточно усталилася офіційна назва — «Ея Императорского Величества войско верных Черноморских казаков», що увійшло в історію як Чорноморське козацьке військо.
У квітні 1788 року почалося створення Чорноморської військової флотилії[15]. Звісно, вона вже не мала старовинних козацьких «чайок» часів Самійла Кішки та Петра Сагайдачного. Ще у 30-ті роки XVIII ст. на Хортиці російські інженери будували для запорожців «новоманерні човні», що поєднували козацькі суднобудівні традиції з європейським досвідом навігаційної науки. Флотилію чорноморців становили легкі судна — шлюпки і дюбель-шлюпки, катери, баркаси, канонерські човни (з франц. canon — гармата). Вони мали гармати і мортири в носовій частині і призначалися для бойових дій на великих ріках, лиманах, частково на морі. Під човни для чорноморців стали також спішно переробляти судна, що виготовляли для розваг і подорожі Катерини II по Дніпру. Як згадував сучасник, ці судна були «конюшня, каретна і спальня для придворної челяді». Отак чорноморці стали єдиними серед козацьких військ Російської імперії, котрі володіли власною флотилією.
У Чорноморському козацькому війську усталився поділ на кінні та піші полки. З піших козаків утворили човнову команду. Оттоді у чорноморців склалися два роди військ: кіннота та, говорячи по-сучасному, морська піхота. Справою кіннотників було бойове забезпечення основної армії, включаючи утримання постів на комунікаціях, доправлення кореспонденції, розвідка і диверсії на ворожій території. А чорноморці човнових команд становили військовий різновид, пристосований не лише до бою на морі, але й для блискавичного десанту на суходіл. Поєднання цих якостей дало чудові результати під час морських баталій і штурму турецьких фортець. Запорожці досконало знали північну частину акваторії Чорного моря, мілини, глибини, особливості берегової лінії Дніпра, Південного Бугу та дельти Дунаю. Ці знання і досвід мореплавання стали у великій пригоді російському командуванню у ті часи, коли Чорноморський флот Росії тільки створювався. Військово-морські сили Росії мали вкрай строкатий склад, включаючи кораблі різних суднобудівних традицій — турецького або грецького, венеційського, французького, шведського типів. Ще задовго до перемог російських адміралів Ушакова та Сєнявіна запорозьким козакам на чолі з Самійлом Кішкою, Петром Сагайдачним та Михайлом Дорошенком вдавалося громити турецькі кораблі на Чорному морі. Та й доти османський флот переважав російський.
Під час османо-російської війни 1787—1791 років колишнім запорожцям довелося воювати на боці двох ворогуючих держав: задунайським козакам — турецького війська, а чорноморським — у складі російського. Проте в разі зустрічі вони намагалися уникати бою.
7 червня 1788 р. козацько-російська флотилія здобула першу велику перемогу у Дніпрово-Бузькому лимані над флотом турецького капудан-паші Ескі-Гассана, на прізвисько «крокодил морських баталій».
Після цих подій Потьомкін пропонував обрати козацьким командиром Харька Чепігу. Коливання між Чепігою та Головатим склали поважну політичну інтригу, але врешті-решт козаки визнали своїм кошовим отаманом Захарія Олексійовича Чепігу, котрий до самої смерті 1797 р. порядкував Чорноморським Кошем. Військовий суддя Антін Андрійович Головатий став командувачем козацької флотилії і незмінним заступником кошового отамана.
Надалі тривали воєнні дії. Успіхи козаків на Березані та при взятті Хаджибею (сучасна Одеса) й Очакова стали яскравими подіями, які змінили хід війни. Утім, після нагороджень й святкувань перемог настали тяжчі часи: недостатнє укомплектування особового складу, нестача провіанту і затримка жалування поставили Чорноморське військо на межу виживання. Ситуація вимагала термінового втручання Потьомкіна. За його наказом, для збору козаків від кожного повіту Катеринославського намісництва були призначені особливі засідателі. Вони отримали повноваження визволяти чорноморців від поміщиків, котрі, скориставшись поверненням козаків до своїх домівок під час зимової відпустки, не забарились записати їх у свої кріпаки. Потьомкін підтвердив своє раніше видане розпорядження приймати у чорноморські козаки усіх вільних людей, крім біглих кріпаків та дезертирів; інколи переходили до чорноморців і козаки з-за Дунаю. Військо поступово кількісно зростало, кінна команда вже нараховувала 2 000, піша — 5000 козаків. Щорічна платня кошового становила 500 рублів, судді — 400, військові писаря, осавулів і полковників — 300, попа — 105, курінних отаманів, довбишів і пушкарів — 30, простих козаків — 12 рублів. Втім, надалі негаразди призводять до бунтів і конфліктів із командуванням.
Восени 1789 року чорноморці перенесли свій Кіш у Придністров’я. Своєю резиденцією Чепіга обрав молдавське селище Слободзею, розташоване за 20 верст від Бендер на лівобережжі Дністра. На козаків чекала найбільш кровопролитна битва за увесь час цієї війни, центральною подією якої став штурм Ізмаїлу.
Втрата Ізмаїла значила для Туреччини кінець усіх сподівань на відновлення колишнього свого панування у Північному Причорномор’ї. Та війна ще тривала. Кошовий отаман Чепіга, отримавши ордени Св. Георгія IV за здобуття Хаджибея і III ступенів за участь в штурмі Ізмаїла, ще відзначився у Мачинській битві 1791 року. Тут йому довелося відбивати атаки турецької і татарської кавалерії, а також битися із задунайськими запорожцями. Як він звітував, «убитих тіл ворога пребагато, у тому числі й невірних запорожців». За цю баталію він отримав орден Св. Володимира III ступеня. Решті чорноморців призначалися золоті хрести за здобуття Ізмаїла. Однак ніхто з козаків ту нагороду не отримав. Російські історики твердять, що сталось це через недбалість Чепіги та Головатого. Хтозна, чи так... Та можна бути певним лише того, що царат зазвичай умів вселяти надію на свою вдячність, однак все барився з тим, щоби бути справді вдячним.
