О новейших происшествиях Головатый рассказывал так же подробно. Во время путешествия в том году Екатерины II-й в Крым, Головатый, собрав команду из прежних запорожцев, испросив позволение Потёмкина, встретил при каком-то месте государыню и препровождал её величество, за что и награждён чином капитана, и вскоре поступил в штат светлейшего и, находясь при нём, прокладывал дорогу к возобновлению казачества. «Не будет уже это Сечь, — говорил Головатый, — но особенное войско из прежних запорожцев; они будут иметь свою оседлость и порядок службы, приличный времени и обстоятельствам».
Головатый, предусматривая, что будущее войско должно быть в теснейшей прежнего связи с армиею и вообще с Россиею, нашёл необходимым и выгодным дать сыну своему, старшему, высшее, нежели бы мог доставить в своём кругу, образование. Слыша о Харькове, где издавна были отличные учебные заведения, он приехал познакомиться с отцом моим и, по его совету, определить сына в училище. Во время пребывания его у нас осматривали пансионы и училища, и с общего совета Головатый избрал так называемые «классы», что ныне гимназия, и где преподавались те же предметы, что и ныне; главный же надзор за сыном поручен был директору классов, полковнику фон Буксгевдену, у которого он и жить должен был.
По отъезде Головатого, вскоре сына его привезла жена Головатого и оставила на попечении отца моего.
С того времени дружеская переписка Головатого с отцом моим продолжалась безостановочно. В письмах своих он всегда величал отца моего: «вельможный батьку!» и своими выражениями всегда извещал о происходившем с ним. Потёмкин, зная его давно, допускал его часто к себе. Вскоре учреждено и составлено «войско верных черноморских казаков». В нём были конные и пешие полки, гребная флотилия, которою командовал Головатый, бывший в новом войске уже «войсковым судьею». «Кошевым же атаманом» был сперва известный Белый, а по смерти его, случившейся вскоре, избран войском Захар Чепига.
В продолжение осады Очакова, князь Потёмкин говорил однажды, что турки из укрепления Березань, близ Очаковской крепости, делают большие беспокойства.
— Головатый! — примолвил князь, обращаясь к нему,— как бы взять Березань?
— Возьмемо, ваша светлость! А чи буде ж крест за те? — спросил Головатый прямо.
— Будет, будет; только возьми.
— Чуемо, ваша светлость! — сказал Головатый скромно, поклонился и вышел.
Немедленно послал он разведать о положении Березани и узнал, когда большая часть гарнизона вышла из Березани для собрания камыша. Головатый поспешил с флотилиею своею, пристал спокойно к берегу, без всякого шума высадил отряд и без дальнего сопротивления завладел укреплением. Отпустив суда свои, переодел своих турками и поставил из них караулы. Гарнизон возвратился и, не предполагая ничего, беспечно входил малыми частями в укрепление. Головатый забирал их по частям и, управившись как должно, с ключами укрепления спешил к Потёмкину.
Входя в ставку светлейшего, Головатый начал петь громким голосом церковную песнь: «Кресту твоему поклоняемся, владыко!» — и, поклонясь низко Потёмкину, положил к ногам его ключи занятой Березани и своими словами, с приличными поговорками и уподоблениями, донёс о действиях своих и в заключение повторил: «Кресту твоему поклоняемся».
— Получишь, получишь, — сказал князь и по статуту возложил на него орден св. Георгия 4-го класса.
Так названное войско верных черноморских казаков делало своё дело на суше и на море; милости князя Потёмкина и награды за службу изливались обильно как на войско, так и частно на храбрейших и отважнейших. Головатый был уже армии полковник и, кроме св. Георгия, имел Владимира 3-ей степени.
Князь Потёмкин, получив титул «великого гетмана», учредил при себе из разных казацких полков «гетманский конвой»; в том числе была «конвойная команда черноморского войска» в блестящих особых мундирах.
Многие чиновники черноморского войска, имея должности по полкам своим, получали армейские чины и, к обыкновенным мундирам своим, присоединяли армейские украшения, следующие по чину: например, премьер-майоры и секунд-майоры нашивали на чекменях своих галуны, положенные для сих чинов в армии на камзолах. Вообще в войске истреблено было прежнее запорожское неопрятство, особливо в чиновниках, которые в одежде своей придерживались единообразия и применялись в мундирах своих к цветам армейским: шальвары широкие, турецкие и чекмень обыкновенно были красного сукна, а верхняя черкеска, с откидными назад рукавами — у пехотных зеленого сукна, а у служащих в коннице синего, — все обложены по борту снурком золотым или серебряным.