Получив такое разрешение, запорожцы в 1787 г., собравшиеся из России и из-за границы, сначала сформировали волонтерскую команду под предводительством запорожского старшины Сидора Белого, а затем, в следующем году, основали войсковой кош на берегу Бугского лимана в урочище Васильково и произвели выборы атамана. Первым кошевым атаманом был избран Сидор Белой. После сего волонтерская команда была преобразована в войско верных казаков, получившее вскорости название Черноморского.

Это войско поступило в действующую армию под главное начальство самого фельдмаршала князя Потемкина.

Сформировав таким образом казачье войско из запорожцев, Потемкин начал совершенствовать свое «войско верных казаков» и заботиться о них, как добрый отец о своих детях. Он дал этому войску флотилию, артиллерию, вооружил и обмундировал казаков, продовольствовал их и удовлетворял жалованьем.

А так как у этих казаков, при разорении Днепровской сечи, были вытребованы в Петербург войсковые клейноды, то, дабы созданное им войско не оставалось без войсковых отличий, а кошевой атаман без присвоенного ему атаманского знака, Потемкин исходатайствовал им войсковое знамя, булаву для атамана и войсковую печать.

Такова, в кратких чертах, военно-административная деятельность Потемкина. Но самой блестящею эпохой в жизни светлейшего был 1787 год, когда польский король Станислав-Август предложил Потемкину обратить его поместья в Польше в род владетельного княжества, зависимого от короны. Светлейший, отклонивший уже желание Фридриха Великого сделать его герцогом Курляндским, не согласился и на предложение короля Станислава. Отверг предложение, несовместное с верноподданническими обязанностями к русской царице, и счел себя достаточно награжденным, когда императрица, по возвращении из путешествия, велела Сенату изготовить похвальную грамоту с означением подвигов генерал-фельдмаршала князя Потемкина «в присоединении Тавриды к Российской империи, успешном заведении хозяйственной части и населении губернии Екатеринославской, в строении городов и умножении морских сил на Черном море». Вместе с тем дано Потемкину наименование «Таврический».

Вскоре после этого началась Вторая турецкая война. Екатерина, пригласив к содействию австрийского императора Иосифа, выставила на юге две армии: украинскую под начальством Румянцева-Задунайского и екатеринославскую под предводительством Потемкина. Но Румянцев, под предлогом болезни, отказался от участия в войне, и тогда обе армии поступили под начальство Потемкина. Он начал с того, что уничтожил рогатки, столь долго тяготившие русскую армию; обратил в казачью службу однодворцев, поселенных по бывшей украинской линии; создал 2-тысячный полк из отставных гусар, сформировал Екатеринославский казачий корпус, вольные греческие, таврические и армянские дивизионы и даже своих крепостных сделал казаками. Все это значительно увеличило наши боевые силы для предстоящей борьбы с Турцией, а рациональность исполненных в войсках преобразований блистательно оправдалась на деле во время последовавшей войны.