Непосредственно после уничтожения Запорожской Сечи Потемкин хотел было уже утилизировать военные силы казачества, приказавши генералу Текелию представить ему список наиболее податливых и отличившихся в последнюю турецкую кампанию старшин, с целью награждения их жалованьем и провиантом. При посредстве таких лиц Потемкин предполагал набрать два пикинерные полка из бывших запорожских казаков. Но на языке запорожцев это означало «поробить их москалями», т. е. сделать солдатами, и поэтому казаки, помнившие, какое участие принимал Потемкин в падении Сечи, не только не поддались на обещание генерал-губернатора, но лишь усилили ряды беглецов в Турцию. Князю Таврическому, однако, удалось окружить себя некоторыми из бывших запорожских старшин, получивших армейские чины, жалованье и составивших у него нечто вроде почетного конвоя; были также единичные случаи поступления запорожцев в Херсонский и Полтавский пикинерные полки и даже на гражданскую службу. Но от всего этого до образования вновь казачьего войска было еще очень далеко. Только мысль об окончательном присоединении Крыма к России и о неизбежности новой войны с Турцией заставила князя Таврического серьезно позаботиться о восстановлении казачества. С этой целью еще в 1783 году Потемкин разрешил бывшим запорожским старшинам: Антону Головатому, Харьку Чепеге и Легкоступу «приглашать охотников к служению в казачьем звании». Впрочем, разрешение это, по-видимому, не дало на первых порах особенно осязательных результатов. По крайней мере до 1787 года об организации вновь зарождавшегося казачества нет достаточных исторических указаний. В этом году, во время путешествия Императрицы Екатерины II по Южной России, Антон Головатый, Сидор Белый и другие казачьи старшины, конечно, не без ведома и содействия Потемкина, поднесли в Кременчуге Государыне адрес, выразив в нем желание служить по-прежнему на военном поле. В том же 1787 году и те же казацкие старшины – Сидор Белый, Захарий Чепега и Антон Головатый окончательно сформировали вольные казачьи команды. Собранные им казаки получили название «войска верных казаков» и были разбиты на две группы – на конницу, под начальством Чепеги, и на пехоту, под командой Головатого; общее же начальствование над казаками было поручено Потемкиным первому кошевому атаману возродившегося войска – Сидору Белому.
Таким-то образом возникло вновь запорожское казачество под именем Черноморского войска, составившего впоследствии основную часть Кубанского казачества. Но прежде чем переселиться в нынешнюю Кубанскую область, черноморцы должны были сослужить службу Русскому государству в борьбе с Турцией. Черноморцы действительно оказали чудеса храбрости в этой войне и на деле доказали свою боевую пригодность и право на самостоятельное существование. Можно сказать, что пролитой здесь кровью они купили себе земли на Кубани.
Ближайшее участие в военных действиях началось для черноморцев с 1788 года. После двух стычек с турецким флотом – 1 июня, когда у Кинбургских берегов турки напали на казачьи лодки и были мужественно отражены казаками, и 7 июня в деле турецкого флота с русской гребной флотилией, за которую казаки получили от Потемкина одобрительный отзыв, 16 июня черноморцы участвовали в поражении турецкого флота. Сражение это отличалось замечательным самоотвержением и стойкостью со стороны русских войск. Командующий русской флотилией, в числе которой были и казачьи суда, принц Нассау-Зиген должен был выдержать напор всего неприятельского флота. Казаки при этом выказали невероятное мужество. На своих мелких гребных судах они смело бросались штурмовать турецкие корабли, сцепившись с которыми, поражали потом неприятеля на палубах собственных его судов… Турецкий флот принужден был отступить с места битвы с большим уроном. Но и казакам недешево далась эта победа, в которой они принимали такое выдающееся участие: войско потеряло кошевого атамана Сидора Белого, получившего в сражении смертельную рану и чрез три дня после того умершего. Спустя 14 дней затем, 1 июля, черноморские казаки снова участвовали в поражении турецкого флота под Очаковом.
Но особенно выказали свои боевые качества черноморцы при взятии Березани. Березань представляла по тому времени почти неприступный остров, находившийся в открытом море, вблизи очаковских берегов. Высокий обрывистый берег этого острова со стороны моря, прекрасная крепость в этой части острова и сильные батареи с юга, по отлогому берегу, доступному для нападения со стороны суши, казалось, делали невозможным сколько-нибудь удачный штурм Березани и тем более для казаков с их небольшими силами и гребными судами. Однако утром 7 ноября, по приказанию Потемкина, казачья флотилия под начальством войскового судьи Антона Головатого смело направилась на остров со стороны суши, несмотря на сильный неприятельский огонь с Березани. Приблизясь насколько позволял этот огонь и глубина моря к отлогому берегу Березани, казаки сделали залп из пушек и ружей, бросились затем в воду, всползли на укрепленный берег и атаковали неприятельские батареи. Рукопашная схватка заставила турок бросить батареи и отступить к крепости, до стен которой преследовали их казаки. Когда турки укрылись за стенами крепости, сильный картечный огонь отсюда принудил казаков воротиться на турецкие батареи. Направивши с батарей турецкие пушки на турецкую крепость, казаки в свою очередь открыли усиленную канонаду. Движение, сделанное со стороны русского флота, от которого отделилось несколько фрегатов по направлению к Березани, и отправление к острову канонерских лодок решили участь турецкого гарнизона: турки сдали остров и крепость казакам.