Чорноморська старшина, козаки добре розуміли, що історія, яка відбулася шістнадцять років тому на Дніпрі, може повторитися й за Бугом.

Царський уряд боявся зростання нової Січі на Україні, тому для війська необхідно було шукати нову землю там, де не зачіпала б козаків панська сваволя, де відчували б вони себе повністю вільними. І тоді, за влучним висловом історика Щербини, запорожці вирішили шукати собі землю в Петербурзі.

Єдиним місцем, яке б задовольнило прагнення козаків до максимальної незалежності, були простори Кубані. Тільки там могли вони почуватись безпечно від найстрашнішого ворога — царських вельмож та панів. План переселення виник у старшин Чепіги і Головатого вже давно, про це думав і отаман Білий. Після тривалих роздумів і суперечок чорноморське товариство вирішило назавжди відмовитися від забузьких земель і вимагати від царського уряду дозвіл на переселення тільки на Кубанські землі. Козацькі дипломати продумали це нелегке завдання до тонкощів, враховуючи і політичні обставини, і психологію царського двору. Але невідомо було, як поставляться до бажання козаків у Петербурзі. І ось знову, як і шістнадцять років тому, вирушив Антін Головатий до столиці з делегацією військових старшин.

Безкінечні канцелярії, велика плутанина, клопоти... Й хоча увішані були царськими орденами та медалями старшини, але відчували вони, що нікому тут не потрібні.

Та мудрий Головатий встиг завести необхідні зв'язки при імператорському дворі і зміг найти найкоротший шлях для вирішення чорноморської справи. Маючи із собою дорогоцінні скарби, військовий суддя досить швидко знайшов для запорожців нових покровителів. Він дарував пихатим вельможам то дорогий турецький ятаган, то коштовну чашу, то баского коня, пригощаючи їх смачними їствами, які надсилали своїм послам чорноморці.

В яскравому козацькому вбранні з блискучою зброєю колоритні запорожці були бажаними гостями у палацах катерининських сановників. Козаки вдавали із себе простакуватих, веселих диваків, любителів пожартувати й погуляти. Розумних же вельмож запорожці дивували своєю освіченістю, мудрістю, поміркованістю у політичних справах, аргументуючи при цьому важливість Кубанських земель саме для чорноморців.

Так, хабарями й подарунками, співами під бандуру, яку Головатий привіз із собою, тонкою психологічною грою делегатам вдалося підготувати сприятливий грунт для успішного завершення цієї нелегкої місії.

Чутки про те, шо у петербурзьких салонах з'явилися дивні козаки, які зачарували всіх своєю дотепністю, розумом і гумором дійшли й до цариці.На святі в Царському селі мав зібратися весь вищий світ, і запорожці, знаючи про це заздалегідь, ще затемна доїхали на конях до Царського села, розташувавшись біля шляху. Коли під'їхали карети з вельможами, козаки на запитання, що вони тут роблять, розповіли про свій злиденний стан, через що їм, мовляв, довелося йти на свято пішки із Петербурга. Розповіді про тяжке становище запорожців дійшли й до цариці, і вона там же призначила аудієнцію й грошове утримання. Так що пізніше Головатий, звітуючи товариству про свою подорож, гордо відзначив, що вони не лише не витратили надані кошем гроші, а й поповнили їх. 2 квітня у петербурзьких салонах помітно пожвавішало — всі прагнули потрапити на аудієнцію до імператриці, де вона мала приймати дивних запорожців. Весь виший світ уявляв, яке враження справлять на Катерину ці вайлуваті козацькі велетні.

Та ніхто не міг того й передбачити. Перед царицею стояли казкові красені, горді, сміливі степові рицарі.

Сам Головатий був у зеленому кунтуші поверх білого жупана, широких шароварах і червоних чоботях із срібними підковками. З довгими вусами й оселедцем, дзвінкою бандурою і коштовною зброєю стояв він, як могутній символ Запорозької Січі.

На прохання Катерини Головатий заспівав свою улюблену пісню про нещасливу долю чорноморців.

Він зачарував присутніх своєю майстерною грою і гарним голосом, сльози текли по його обличчю, Головатий співав про померлого фаворита Катерини.

Розчуливши імператрицю, Головатий звернувся до неї з промовою, побудованою за всіма взірцями європейського етикету: "Жизнедеятельным державного ведення твоего словом, перерожденный из неплодного бытия верный Черноморский Кош приемлет наше дерзновение вознести благодарный глас свой к святейшему Величеству твоєму й купно изглаголити глубочайшую преданность сердец его. Прийми одну яко жертву единой Тебе от нас сохраненную, прийми й уповаючим на сень твою буди нам прибежище, покрор, радование..." .

Катерина була зачарована запорожцями і задовольнила їхні прохання. В імператорській грамоті від 30 червня 1792 р. зазначалося, що чорноморському війську надаються землі Кубані у вічне користування. У своїй грамоті Катерина підтвердила всі прохання козаків.

У вічне користування війську надавався "остров фана-гория со всею землею, лежащей на правой стороне реки Кубань — от устья её к усть-Лабинскому редуту, так, чтобы с одной стороны река Кубань, с другой же Азовское море до Ейского городка служило границей войсковой земли". Таким чином колишні запорожці отримали 2855966 десятин практично незайманої землі, або 28 тисяч кв. верст Кубанської землі .

За новим Чорноморським військом закріплювались старовинні запорозькі привілеї — власне самоврядування і власне військове правління. Війську надавалося право вільного економічного порядкування і торгівлі. Губернатору Таврії доручалося звільнити всіх запорожців від кріпацтва і дозволити їм приєднатися до чорноморців, а війську для переселення на Кубань надавалися кошти у сумі 30 тисяч крб., провіянт і "всевозможные вспоможения".

Пізніше видатний козацький історик напише про наслідки посольства Головатого:

"До известной степени казаки взяли все, что только можно было взять при тогдашней правительственной системе в общих условиях политической жизни. Быть может Черноморцы действительно с чувством удовлетворенных желаний пели "Ой годі нам журитися, пора перестати". Жизнь на Кубани в обособленной, изолированной территории, не могла не улыбнуться казаку".

Козацьких делегатів на зворотному шляху зустрів почесний ескорт у складі 500 чорноморців, при під'їзді до Слободзеї зі стін козацької столиці три рази вдарили гармати. Головатого і старшин радісно зустріли сивовусі січові діди і з хлібом-сіллю. Під святковий вогонь з рушниць і пістолів Головатий ніс на дарованому срібному блюді, у яке, за переказами, Катерина насипала козакам золоті червінці, грамоти імператриці, а сини його несли коштовну шаблю, подаровану кошовому Чепізі.

Чепіга поцілував хліб і зачитав грамоту, потім низько вклонився товариству. Шлях на Кубанські землі для Чорноморського війська був відкритий.

Доки запорозькі депутати в Петербурзі добували для війська нові землі та привілеї, чорноморці відправили на Кубань військового осавула Матвія Гулика з козаками, щоб той уважно дослідив майбутні козацькі землі.

Запорожцям, які були з Матвієм Гуликом, Кубань відразу нагадала центр колишніх запорозьких земель — Великий Луг (Батько). Такі ж як і на Дніпрі густі і широкі плавні, великі степи і ліси з ярами та байраками, і як у Дикому Полі скрізь по кубанських степах височіли могили.

Чорне море, Керченська протока, Азовське море від Тамані до Єйського Лиману, численні солодкі лимани по всьому побережжі, річка Кубань і безліч степових річок свідчили чорноморцям про багаті рибальські промисли. У плавнях навколо соляних озер водилося безліч птиці — диких качок, гусей, журавлів, куликів, лебедів. У лісах, гущавах і пролісках жили дрофи, тетереви, куріпки, фазани. Багато диких тварин — кіз, лисиць, зайців, вепрів, ведмедів — робили Кубанщину справжнім раєм для мисливців. У соляних озерах по Азовському узбережжю були поклади солі.