Постройка храма, однако, задержалась. Только на 29 июля 1800 года назначена была закладка в Екатеринодаре церкви Воскресения Христова, причем требовалось еще отыскать мастеров для высечения камня и отливки оловянной тарелки под фундамент здания. Войсковое Правительство распорядилось вместе с тем пригласить из куреней стариков и казаков для участия в этом торжественном войсковом акте. Но уже в следующем, 1801 году, раскрыты были обстоятельства, бросившие неблаговидную тень на строителей и обнаружившие крупные недостатки в строительстве. Посланный в войско генерал Кираев донес генерал-прокурору Святейшего синода о злоупотреблении и ошибках при постройке Екатеринодарской церкви. Строилась, по словам Кираева, «преогромная деревянная церковь архитектурой подобная той, какова была в старой Запорожской Сечи». Постройка была задумана неразумно и нерасчетливо. Благодаря дороговизне леса, получаемого с Волги и обходившегося по 6 р. за бревно, на те средства, которые были затрачены на церковь, давно уже можно было бы построить превосходный каменный из жженого кирпича храм. На церковь Войсковым Правительством было отпущено 30 000 рублей, а издержано было уже более 60 000 рублей — церковь при этом не достроена. В результате приказано было местному архиерею расследовать дело.
Из рапорта подрядчика сотника Плетневича в войсковую канцелярию от 13 февраля 1807 года видно, что в этом году иконостас в Екатеринодарском соборе был окончен.
Более серьезную задачу в деле церковного строительства и религиозных установлений представляло устройство обители войском. Запорожцы имели свой монастырь — Самарскую Николаевскую пустынь, которую поддерживали щедрыми пожертвованиями и в которой наиболее религиозные представители казачества оканчивали свои дни, принимая монашество и схиму. Черноморцы пожелали иметь такую же свою собственную обитель, мотивируя необходимость ее тем, что многие престарелые и раненые казаки желали окончить жизнь свою в монашеском чине. Местом для нее было избрано красивейшее урочище у так называемого Лебяжьяго лимана, напоминавшего своей фигурой лебедя и изобиловавшего лебедями. Поэтому и самый монастырь был назван Екатеринолебяжинской пустынью. Черноморцы пожелали устроить свой монастырь по образцу Саровской пустыни. Из указа Синода от 7 августа 1794 года видно, что прежде чем Войсковое правительство обратилось в Синод с просьбой о разрешении устроить обитель, оно просило о том же и государыню Екатерину II, которая и дала разрешение на это указом на имя Святейшего синода. Синод, следовательно, только исполнил волю царицы. На основании этого указа было предписано Иову, епископу Феодосийскому и Мариупольскому, выяснить: 1) что и где представляло собой место для устройства обители на строителя, 30 монахов и 10 больничной братии и 2) какое лицо желало Войсковое Правительство представить в настоятели. В следующем году отношением Феодосийской консистории за подписью иеромонаха Коментария было сообщено Войсковому Правительству, что, согласно просьбе войска, возведен в сан архимандрита избранный войском иеромонах Феофан, бывший настоятелем Самарского Николаевского монастыря и назначенный настоятелем Черноморской монашеской пустыни. 26 мая 1796 года епископ Иов известил Чепигу, что он согласен наименовать казачий монастырь Екатерино-Лебяженской Свято-Николаевской пустынью и велел архимандриту Феофану приступить к постройке в ней третьей церкви во имя великомученицы Екатерины. В том же, 1796 году, епископ Гервасий послал в помощь архимандриту Феофану иеромонаха Иосафа и иеродиакона Галактиона. В ноябре того же года войсковой атаман Чепига просил епископа Гервасия назначить, вместо одряхлевшего и больного Феофана, другого настоятеля.
С своей стороны и войско старалось пополнить ряды монашествующих местными представителями. Так 5 февраля 1797 года шесть престарелых казаков из куреней Джерелиевского, Васюринского, Ивановского, Незамаевского и Каневского были освобождены Войсковым Правительством от военной службы и зачислены в состав монашествующей братии Екатерино-Лебяженской пустыни, где до того они несли обязанности послушников.