Не успели черноморцы опомниться, обжиться или устроить свой быт, как получили приказание готовиться к новому переселению, на Кубань. Вместе с тем прошли недобрые слухи, что казачий уряд будет вовсе уничтожен, что из них составят легкоконные полки для охранения Кубани, куда станут посылать их поочередно. Войско собралось на раду печальное, убитое; приговор рады был таков же: «Что будет, то будет, а будет то, что Бог даст». Однако, они тотчас же выслали есаула Гулика для осмотра пожалованной земли, а в то же время обрядили в Петербург депутатов с тем, чтобы они испросили грамоту на вечное владение. В депутаты выбрали Головатого, двух майоров и 5 казаков.
Пока есаул Гулин странствовал по диким пустырям Черноморья, Головатый с товарищами распинались в столице за судьбу своего войска. Долго они не могли получить доступ к Императрице. Вельможи пышного двора недоумевали, как можно ввести во дворец этих полудиких людей? Головы у них бритые, говорят они не по-людски, точно мычат, вместо, ответа: «Эгэ», «та ни», «а тожь» – таких слов, ведь, никто не поймет! Однако Головатый, благодаря старым знакомствам, добился, что прием депутации был назначен в одно из воскресений.
Наступил желанный день. Съехались во дворец придворные, чужеземные посланники, министры, съехался весь генералитет. В тронной зале чинно все ожидали выхода Императрицы. Вдруг входят в залу черноморцы: впереди Головатый в зеленом чекмене (бешмете), обшитом полковничьими галунами, в белой черкеске, широких шароварах и в красных с серебряными подковами сапогах. Весь обвешанный орденами, покручивая свои длинные усы, он сурово посмотрел на всех и стал на указанном месте. Обедня кончилась, говор в зале утих, и вот Государыня величественно вступила между двумя рядами. Медленно и с кроткой улыбкой она подошла к черноморцам. Старый запорожец оживился, его глаза заблистали радостью, он громко и ясно произнес по-русски приветствие от своего коша. Государыня ласково выслушала и подала ему руку.
Головатый упал на колени, залился слезами, причем троекратно облобызал царскую руку. Государыня еще с минуту простояла, потом удалилась в свои покои. В тот же день была объявлена воля Императрицы, чтобы Головатый подал записку о нуждах войска Черноморского. Записку сейчас составили и подали куда следует. В ней Головатый изобразил жалкое положение бывших сечевиков, принужденных поспешно подниматься в далекую окраину, распродавать скот, свои убогие пожитки, а надолго ли? – про то они не ведают.
Пока записка ходила по рукам, Головатый проживал в столице. Все знаменитые вельможи наперерыв зазывали его к себе на обеды, на вечера, с жадностью слушали его рассказы про Сечь, про нравы и обычаи запорожцев. Большинство русских людей того времени признавало в них не больше как разбойников, буйных, непоседлых. Часто Головатый брал с собой бандуру и, по просьбе хозяев, певал старые казацкие песни, то заунывные, от которых щемило сердце и навертывались слезы, то разгульные, от которых кружилась голова, сами собой ходили ноги. Депутатов приглашали на все придворные празднества. Особенно ласково относился к ним Великий Князь Константин Павлович. Однажды, проходя мимо Головатого, он завертел пальцами, точно хотел завернуть за ухо чуприну, причем спросил у него, отчего это черноморцы завертывают свою чуприну за левое ухо:
– Все знаки достоинства и отличий, Ваше Высочество, как-то: сабля, шпага, ордена, носятся на левом боку, то и чуприна, как знак удальства и храбрости, должна быть завернута за левое ухо.
Императрица узнала, что Головатому хочется заглянуть в ее комнаты, и тотчас приказала показать депутатам весь дворец, сверху донизу. Когда их ввели в ее собственный кабинет и показали на стол, где пишет Государыня, Головатый схватил перо, благоговейно его поцеловал и положил обратно на стол.
30 июня 1792 года в Сенате был получен Высочайший указ, в котором говорилось, что войску казачьему Черноморскому, собранному покойным генерал-фельдмаршалом князем Потемкиным из верных казаков бывшей запорожской Сечи, дана жалованная грамота на остров Фанагорию со всеми угодьями и землями между Кубанью и Азовским морем. А в грамоте, данной черноморцам, после перечисления их боевых заслуг, было сказано, что: «…войску Черноморскому предлежит бдение и стража пограничная от побегов народов закубанских; на производство жалованья кошевому атаману, войсковым старшинам и прочие по войску расходы повелевается отпускать по 20 тыс. рублей на год; предоставляется пользоваться свободною торговлею и вольною продажею вина на черноморских землях; равно впадающих в погрешности судить и наказывать войсковому начальству, но важных преступников отсылать к губернатору Таврическому. Высочайше жалуется знамя войсковое и литавры, кроме тех знамен, булавы, перначей и войсковой печати, которые от покойного фельдмаршала, по воле Императрицы, уже войску доставлены».