В 1863 году в Екатеринодаре было открыто Мариинское женское училище. Названо Мариинским по имени государыни императрицы Марии Федоровны (1759-1828), супруги Павла Первого, создавшей целый ряд учебно-воспитательных и благотворительных заведений. Оно растило и воспитывало юных казачек в духе любви к земле Кубани, к русской культуре, к семье, к родному очагу.  В училище принимались девочки из семей всех состояний и вероисповеданий в возрасте от семи лет. В учебном заведении существовали попечительный и педагогический советы, куда входили представители Кубанского казачьего войска. В течение сорока лет занятия проводились в специально построенном здании на углу Маринского бульвара и улицы Почтовой (Октябрьской и Постовой). Но к началу ХХ века в связи с резко увеличившимся количеством воспитанниц стала ощущаться нехватка учебных помещений. Требовалось строительство нового более просторного здания.

16 сентября 1906 года благодаря поддержке Наказного Атамана кубанского казачьего войска Якову Дмитриевичу Маламе состоялась торжественная закладка здания Кубанского Мариинского женского института. Его проект разработал известный Кубанский архитектор Александр Петрович Косякин, уже тогда зарекомендовавший себя оригинальными постройками уютных школьных помещений и красивых станичных церквей. Александр Петрович решил отказаться от стандартов и шаблонов, уже много десятилетий царивших в строительном искусстве России. Талантливый зодчий создал свой собственный оригинальный проект. Все лепные работы, двери, окна, кронштейны и другие фигуры, украшающие фасад созданы Косякиным совершенно самостоятельно.

Строительство здания Мариинского института длилось три года. Александр Косякин стремился, чтобы каждая часть здания точно соответствовала техническому чертежу, тем размерам и формам, которые были заданы самим архитектором. И его труды не пропали даром. В 1909 году Екатеринодар получил одно из самых красивых зданий в своей истории.

К сожалению, революционные бури привели к закрытию Мариинского женского института, а в его здании разместилась партийная школа. В годы Великой Отечественной войны здание довольно сильно пострадало, но было успешно восстановлено в 1950 году уже как здание Высшего военного училища имени С.М. Штеменко, которое готовит специалистов-шифровальщиков для наших Вооруженных Сил.