Бывшее Екатеринославское казачье вой-ско имеет свою историю. Оно возникло одновременно с Черноморским войском и под влиянием тех же причин, как это последнее. Казаки потребовались для войны с турками. В то время, когда Черноморское войско формировалось исключительно из бывших запорожских казаков, Екатеринославское войско составилось из всевозможной вольницы. В него вошли вольные искатели приключений – малороссийские казаки, беглые крестьяне, однодворцы, старообрядцы, мещане и вообще разные выходцы на юг России. Добровольцы эти в 1788 году, в начале войны с турками, соединены были с Бугским казачьим войском и все вместе получили название сначала Бугского, а потом Екатеринославского казачьего войска. Екатерино-славское войско выставляло десять полков, тысячного состава каждый, и насчитывало до 50 562 д. обоего пола населения.

Благодаря разнообразному составу и массе не казачьих элементов в рядах Екатеринославского войска почти не оказалось своей старшины. Не из кого было выбирать офицеров. Так как Екатеринославское вой-ско оказалось смежным с Донским, то оно подчинено было этому последнему и называлось Екатеринославским или Новодонским войском. Донские старшины, по назначению правительства, управляли екатеринославцами и, как с пасынками, не стеснялись с чуждым им казачеством. Появились поборы, утеснения, назначения на службу не в очередь и т.п. В течение 8 лет этого зависимого положения екатеринославцам показалось настолько тяжелым донское иго, что они начали ходатайствовать о возвращении их «в первобытное состояние». Казаками пожелали остаться только бывшие бугские запорожцы. Тогда Екатеринославское войско снова было подразделено на две части: на Бугское войско и на пришлые элементы, составившие Екатеринославское войско. Первые, бугские запорожцы, были оставлены, согласно их желанию, в казачьем звании, а вторые, собственно екатеринославцы, переведены на казенный оклад на правах однодворцев. За прежнюю военную службу им дана была только двухлетняя льгота от подушного оклада.

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

С этой целью Сенат предварительно собрал сведения о просителях через Слободского украинского губернатора и об условиях поселения казаков на Кавказе через губернатора астраханского. Первый ответил условно, что переселить их можно столько, сколько окажется в излишке, за наделением всех однодворцев 15‑десятинным наделом. Второй, астраханский губернатор Повалишин, донес о запросе Сената астраханскому военному губернатору и инспектору Кавказской дивизии г.-л. Кноррингу. Генерал Кнорринг воспользовался удобным случаем. Давши краткий очерк об условиях заселения Кавказа от Кизляра до Усть-Лабы казаками Кизлярского, Терского и Гребенского войск и Моздокского, Волгского, Хоперского и Кубанского полков, располагавших 248 старшинами и 4246 казаками служилого состава, он признал, что от переселения на Кавказ казаков бывшего Екатеринославского войска «важные произойдут пользы для границы». Самым расположением новых станиц по Кубани, между Кавказской и Усть-Лабинской крепостями, можно было уже загородить черкесам проход в русские владения на протяжении 90 верст. Затем новоселы могли образовать целый казачий полк пятисотенного состава, и часть полка могла быть назначена в другие места для защиты границы. Мнение генерала Кнорринга имело решающее значение для екатеринославских казаков.

После того как Сенат собрал все справки о переселенцах и доклад его по этому предмету представлен был Государю, 16 октября 1801 года Александр I утвердил мнение Сената, и вопрос о переселении бывших казаков Екатеринославского войска на Старую Линию был решен в положительном смысле.

Желающих переселиться на Кавказскую кордонную линию из пяти сел Изюмского уезда – Сухаревки, Терской, Ямполовки, Краснянской и Дериловой – записалось 770 душ муж. пола, и из шести сел уезда Старобельского, Новоайдарского, Спеваковки, Бахмутовки, Райгородской, Староайдарской и Трехизбенской – 2530 д., а всего 3300 д. м. пола. Но когда Старобельский нижний земский суд «сочинил» свои списки переселенцев, то в них попали однодворцы из других селений и даже из другого, Змиевского, уезда. Таких добавочных селений оказалось 7 по Змиевскому уезду и 4 по уезду Изюмскому, с 479 душами м. п. в обоих. Права на переселение Слободскоукраинским губернским правлением были признаны лишь за 3300 д. м. п., из числа их приказано было выбрать надежных доверенных лиц для осмотра мест поселения на Старой Линии.

Доверенными были есаул Гречишкин и сотник Фарафонов «со многими стариками». Ими осмотрены были как весь подлежавший заселению район, так и места, предназначенные под станицы. Станицы должны были находиться на известном расстоянии друг от друга и непременно близ существовавших уже укреплений. Екатеринославцам указаны были 4 редута: Ладожский, Тифлиский, Казанский и Темишбекский, при которых предполагалось расположить станицы. Доверенные, со своей стороны, нашли места эти подходящими для этой цели. Оставалось только переселить население бывшего Екатеринославского войска, находившееся еще на старом местожительстве. Осмотр мест новоселами производился в апреле и мае месяцах, а в сентябре и октябре 1802 года, как донес об этом в Тифлис генерал Кнорринг, на Кавказскую линию прибыли бывшие екатеринославские казаки и основали при 4 редутах 4 станицы, без всякой помощи казны, на собственные средства.

Но выбор мест под станицы не обошелся без затруднений. Г.-м. Шеншин в рапорте 13 августа из Усть-Лабы сообщил Кноррингу, что место под станицу Тифлисскую, разрешенное им для заселения, согласно желанию переселенцев, внизу у берега Кубани, он считал неудобным и полагал бы расположить станицу выше и ближе к редуту, под защиту его. То же писал Кноррингу о расположении станицы Темишбекской полковник Дияков. Место, первоначально избранное для этой станицы, он нашел низким, сырым и нездоровым. В низинах и впадинах, при дожде и грязи, могли образоваться топи и лужи, грозившие людям «тяжкими болезнями». К тому же местоположение это неудобно было и с точки зрения охраны его от горцев, как удаленное от укреплений и требовавшее особого охранного отряда. Сообразно с такими указаниями Шеншина и Диякова и было изменено расположение станиц Тифлисской и Темишбекской.