По указанию императрицы Екатерины II в излучине реки Кубань 9 июня 1793 года началось строительство крепости Екатеринодар. Укрепление должно было стать местом, где находилось административное управление войском, куренями и важнейшие учреждения. Собственно городом Екатеринодар и считался лишь потому, что в нем находилась крепость и войсковое правительство.

По окончанию победоносной русско-турецкой войны Екатерина II приняла решение о переселении черноморских казаков на Кубань, для охраны расширившийся на юг русской границы. Атаман Захария Чепега принял самое активное участие в организации переселения и основании Екатеринодара.

Екатеринодарская крепость расположилась в излучине Кубани, пересекаемой с северо-востока Карасуном, а с запада ее закрывали река и Ореховатая балка. Земляное укрепление было создано по правилам фортификации конца XVIII - начала XIX веков в согласии с традициями Запорожья. По своему месторасположению и плану крепость очень напоминала Новую Сечь. Она стояла на возвышенном месте обособлено от городских кварталов, закрывая последние своими укреплениями со стороны речной поймы.

У крепости имелись укрепленные ворота - башта. В самой крепости как и в Сечи вдоль валов стояли курени, образуя собой квадрат. В центре была установлена походная Троицкая церковь, замененная затем большим деревянным Вознесенским собором.

Рядом с войсковым собором, еще в годы его закладки, появилось мемориальное кладбище, на котором хоронили наиболее достойных казачьих деятелей. Здесь был погребен кошевой атаман - основатель города Захария Чепига, позже А. Высочин, Тимофей Котляревский и Роман Порохня, Кирилл Россинский, Яков Кухаренко, Николай Успенский и Николай Рябовол.

Долгое время войсковое правительство добивалось, чтобы атаманы куреней и куренные администрации располагались в специально построенных в крепости 40 зданиях. Однако на Кубани не удалось восстановить традиционное запорожское управление, и деревянные курени-казармы пустовали, приходя в негодность. Тем не менее, уже в 1816 году на их месте были построены кирпичные здания, первые в Екатеринодаре.

В начале XIX века в Екатеринодарской крепости кроме куреней, войскового собора, находились: денежная кладовая, пороховой погреб, артиллерийский арсенал. Позднее сюда был переведен войсковой госпиталь, и большая часть куреней стала больничными палатами. В других зданиях крепости, фигурировавших в документах как флигели и полуфлигели, разместились: архив, гауптвахта, аптека, гимназия, военно-фельдшерская школа.