9 декабря 2001 года митрополит Екатеринодарский и Кубанский Исидор (Кириченко) освятил место для строительства монастыря в Апшеронске и внес первые 30 000 рублей на его возведение.

12 марта 2002 года Священный Синод РПЦ МП принял решение об открытии в Апшеронске женской обители, посвященной Пресвятой Богородице и иконе «Нерушимая Стена». Проект застройки разработал архитектор Ю. С. Субботин.

9 июня 2002 года у освященных полгода назад закладного камня и поклонного креста прошла первая Божественная литургия, которую провел игумен Соловецкого Спасо-Преображенского мужского монастыря Зосима (Чеботарь). Символическими Царскими вратами алтаря служили две высокие ели в восточной части обители.

26 июля 2002 года был заложен первый монастырский храм в честь святого пророка Илии. 6 июня 2004 года митрополит Исидор освятил построенный Ильинский храм.