Сначала казачьи просьбы были гласом вопиющего в пустыне. Но в 1803 году на помощь черноморцам пришел граф Ланжерон. В своем рапорте Государю от 8 августа 1803 года он говорит, что прежде был сильно предубежден против черноморских казаков, но, присмотревшись ближе к этому войску, он нашел нелепыми слухи о его неблагоустройстве. Ланжерон называет Черноморию «благоустроенной колонией», которая создала ряд «хороших и обширных селений», завела хозяйство, соорудила 29 храмов и 1 монастырь, развила промыслы, увеличила до 84 000 рублей войсковые доходы и, что особенно важно, успела «приучить к себе дикие народы Кавказа». Располагая 20 полками, войско выставляло ежегодно 7 из них для охраны границ в кордоны. На этом основании Ланжерон просил Государя уважить ходатайство казаков и перевести из пределов Черномории оба егерских полка. Один полк Ланжерон просил перевести в Крым, а другой поместить в Фанагорийской крепости, расширивши новыми пристройками казармы и принявши на счет казны отопление их.

Ходатайство графа Ланжерона уважено было лишь по одному пункту. Указом Военной коллегии 21 сентября 1803 года приказано было, в облегчение Черноморского войска, принять на казенный счет отопление егерских казарм и жилищ. Войска же оставлены были в казачьих поселениях.

Между тем, при крайней неопределенности порядков по формированию частей для кордонов и в полки, страдало прежде всего само население, не знавшее заранее, когда и сколько из его рядов потребуется сил. Ставилось в затруднение и военное начальство, так как в одних случаях получались недоборы, в других на службу попадали не те лица, которые должны были отбывать ее, в третьих – оказывались лица непригодные для службы и т.п. Требовался, одним словом, постоянный штат казачьих кадров. Центральное правительство ввело его. Высочайшим повелением 16 апреля 1801 года было утверждено мнение Военной коллегии о сформировании в Черноморском войске постоянных 10 конных и 10 пеших казачьих полков. В следующем, 1802 году, были сформированы и самые полки. Высочайшим указом 13 ноября этого года повелено было:

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

В состав каждого полка ввести 1 полковника, 5 полковых есаулов, 5 сотников, 5 хорунжих, 1 квартирмейстера, 1 писаря и 483 казака.

Казачьи чины приравнять: полковничий и войскового старшины к майору, полкового есаула к ротмистру, сотника к поручику, хорунжего к корнету, а квартирмейстера, как в регулярных войсках.

Всех старшин, служивших в войске, приказано возвести в соответствующие чины и «впредь ни в какие офицерские чины по войску не производить», а производство представлять на усмотрение Государя Императора.

В казачьих конных полках, находящихся на службе далее 100 верст от места их выступления, определено выдавать жалованье и содержание офицерам как в гусарских полках, писарю – 30 р. в год и провиант, казакам 12 р. в год, провиант и фураж на две лошади – на одну натурой и на одну деньгами. Жалованье и содержание пехотных полков приравнено к полкам регулярной армии.

В случае общей войны такое же содержание должно производиться казачьим войскам, раз они будут двинуты на войну, посажены на суда, отряжены по особому назначению и пр.

К концу года полки окончательно были сформированы, и 15 мая было назначено днем ежегодной смены по очередям полков, посылаемых для кордонной службы.

Полковым устройством до известной степени было урегулировано правильное отбывание казачьим населением очередной службы на Линии и в кордонах. Но сама по себе кордонная служба, кроме внутренних по каждому кордону распорядков, требовала известного надзора и общего руководства по всей пограничной линии.

Первоначально на всю Кордонную линию назначался один главный начальник. Таким начальником состоял в первое время заселения края известный старшина Мокий Гулик. Позже фактически им был наказной атаман Бурсак, человек энергичный, деятельный и неутомимый. С 1806 года вся Кордонная линия была разделена на части или группы и в каждую часть назначался особый начальник, в ведении которого находились кордоны его части. Таких частей было четыре и распределение по ним кордонов было произведено в следующем порядке.

В часть 1‑ю входили кордоны Редутский, Изрядный, Воронежский, Подмогильный, Константиновский, Александрин, Павловский, Великомарьинский, Екатеринодарский и Александровский. К этой же части были причислены два кордона, расположенные внутри Черномории – Кочатинский и Кирпильский.

К части 2‑й отнесено было только четыре кордона: Елизаветинский, Лагерный, Елинский и Марьинский.

К части 3‑й причислено столько же: Новоекатерининский, Ольгинский, Славянский и Протоцкий.

Наконец, часть 4‑ю составили семь кордонов, находившихся на Таманском полуострове: Копыльский, Петровский, Староредутский, Андреевский, Смоленский, Новогригорьевский, Бугазский.

Такое распределение кордонов на части произведено было сообразно с особенностями местностей. В первой части кордоны были расположены близко один возле другого, местность была большей частью открытая и с высоким берегом Кубани. Следить за движениями черкесов за Кубанью и предупреждать нападения их на край здесь было легче, чем в других местах. Притом же в Екатеринодаре жил сам наказной атаман. Вторая и третья части находились в иных условиях. Здесь и по левую и по правую сторону Кубани было много плавней и мест, удобных для скрытого прохода черкесов большими партиями. Части составлены из четырех кордонов каждая, так чтобы начальник части мог во всякое время скорее объединять действия всех кордонов и быстрее передвигать, в случае нужды, казачьи команды в места появления черкесских партий. В таких же условиях находился и Таманский полуостров.

Сообразно с этим, по кордонам распределялись и боевые силы, о чем можно судить по двум ведомостям о числе конных и пеших казаков за два года.

Таким образом, по этим цифрам видно, что, независимо от количества кордонов, каждая часть их обслуживалась приблизительно одинаковыми по количеству силами. При большем количестве кордонов в первой части приходилось на кордон в среднем меньше, чем во второй и в третьей частях. Так, в 1807 году в первой части на кордон приходилось 135 казаков, в третьей – 215, а во второй – 313 человек. Очевидно, распределение казаков по кордонам и частям сообразовалось с условиями охранной службы и борьбы с черкесами. В кордонах второй и третьей частей было наибольшее количество казаков, потому что им приходилось охранять большие пространства и требовался более усиленный дозор.

Вообще кордонная служба сопровождалась частыми переменами во всем – и в общем составе охранных сил, и в размещении их по кордонам, и даже в назначении укреплений. В 1806 году по ведомостям значилось на Кордонной линии 2170 конных казаков и 641 пеших, в 1807 году 2730 первых и 1597 вторых, при 108 офицерах, а в 1808 году 2586 конных казаков и 1022 пеших, при 99 офицерах. Чем спокойнее было в горах, тем меньше требовалось охранной стражи, и наоборот.