Введенская церковь, достоявшая до наших дней, хоть и в очень искаженном виде, располагается недалеко от древнего Иоанно-Предтеченского монастыря. С основанием этого монастыря в 1688 году при нём сразу же начала образовываться небольшая слобода из работных людей. Большинство из её жителей были плотниками и занимались тем, что строили на протекавшей рядом реке Луковке, по заказам купцов и промышленников торговые и промысловые речные суда. В течение XVIII века эта слобода всё более увеличивалась, для удовлетворения духовных потребностей жителей при Иоанно-Предтеченском монастыре жил особый священник с причтом. В середине XVIII века здесь были размещёны солдаты Астраханского линейного батальона. Оттого эта слобода стала называться Солдатскою. В конце XVIII века для жителей слободы появилась возможность устроить здесь свой приходской храм.

В 1791 году за малолюдством прихода была упразднена Никольская церковь, что в Шепиловой слободе. Шепилова слобода была одною из древнейших в Земляном городе. Основана она была в 40-х годах XVII века, и жители её в основном были стрельцы. Никольская церковь в Шепиловой слободе упоминается уже в 1671 году. После подавления стрелецкого восстания в Астрахани в 1706 году много дворов в слободе запустело и их спешно стали заселять расквартированными в то время в городе солдатами. Чуть позже здесь во множестве стали селиться армяне. К концу XVIII века Никольская церковь осталась практически без прихода. Само здание церкви вместе с церковной утварью купил астраханский купец Фёдор Алексеевич Неверов для переноса, по его желанию, в станицу Лебяжинскую. Но формально Никольская церковь переносилась в Солдатскую слободу, где, с благословения архиепископа Платона (Любарского), была построена деревянная церковь в честь Введения во храм Пресвятой Богородицы. Освящёна она была 21 ноября 1797 года самим архиепископом Платоном. Новоустроенная церковь была снабжена церковной утварью: частью оставшейся от упразднённой Никольской церкви, а частью – от Троицкого монастыря.

Но построенная церковь не могла вместить всех прихожан, и, так как не имела отопления, в зимнее время во время богослужения и священнослужители, и прихожане её терпели великую нужду от холода. Поэтому в 1805 году в трапезе храма были устроены два тёплых придела: правый в честь Равноапостольных царей Константина и Елены, а левый в честь Благоверного Великого князя Александра Невского. Первый был освящён архиепископом Платоном 2 июля 1805 года, а второй – благочинным протоиереем Василием Панфиловым 3 июля того же года. Деньги на их строительство собраны были от жертвователей.

В 1814 году подгнили венцы в фундаменте церкви и возникла опасность ее разрушения. Вследствие этого, благочинный протоиерей Андрей Бедняков и церковный староста купец Николай Шайкин 7 июля 1814 года обратились к Астраханскому архиепископу Гаию (Токаову) с просьбой выдать им сборную книгу на построение нового каменного Введенского храма. 30 июня 1817 года тем же лицам была выдана храмоздательная грамота. 4 сентября 1818 года было заложено основание храма. Основные строительные работы вёл астраханский подрядчик Филипп Петров, а главным жертвователем на строительство храма стал астраханский купец Иван Львович Михайловский. После построения каменной трапезы в ней были устроены два боковых придела, которые были освящены: правый в честь Равноапостольных Константина и Елены 16 января 1819 года протоиереем Фёдором Александровым, а левый в честь Благоверного князя Александра Невского 19 января им же. Сам храм был закончен постройкою в 1822 году и освящён Астраханским архиепископом Авраамом (Шумилиным) 14 мая.

В 1872 году к колокольне Введенского храма с левой стороны была пристроена каменная палата для церковной ризницы. В 1902 – 1903 годах расширена была трапеза храма с обеих сторон, с перенесением обоих придельных алтарей на один уровень с центральным. Боковые приделы были освящены: правый в честь Фёдоровской иконы Божией Матери, а левый в честь Равноапостольных царей Константина и Елены.

Внешний и внутренний вид храма

Введенский храм был построен по одному архитектурному плану с храмом Иоанна Златоуста, но многочисленные перестройки как в том, так и в другом храме со временем сильно изменили первоначальный облик церквей. Введенский храм архитектуры классической с двухъярусной колокольней в одной связи. Расписан он был в 1821 году иконописцем Авакимом с товарищами. В 1903 году на расширенной части храм был заново расписан с подновлением прежней росписи. В 1912 году был сооружён новый центральный иконостас из фарфора, покрытый розовой и голубой эмалью с позолотой. В 1923 году Введенский храм был захвачен обновленцами и находился в их ведении до 1939 года.

По свидетельству А.И. Кузнецова, этот храм сдал властям под гараж «обновленческий проходимец некто Рыбаков». «Как-то ехал я на трамвае, – рассказывал Кузнецов в 1939 году. Ко мне подошёл средних лет мужчина в хорошем пальто и шляпе и вдруг ни с того ни с сего обратился ко мне с такими словами: "По одежде и по портфелю вижу я, что вы человек с положением. Не можете ли вы указать мне, где бы я мог найти работу по должности начальника снабжения, завхоза, агента. Я бывший поп, долго морочил людям голову. Сам ни во что не верил. Надоело это мне, пошёл я на днях в горсовет и отдал ключи от церкви Введения, дескать, никому церковь не нужна. Теперь там – гараж". Я спросил его фамилию, громко назвал его негодяем и подлецом и вышел из вагона». После своего закрытия Введенский храм был передан автошколе на арендных основаниях, а 11 августа 1953 года Астраханский облисполком своим решением постановил полностью переоборудовать церковное здание по ул. Грузинской, 27 под автошколу «Глававтотранскадры». В результате этого переоборудования колокольня храма была снесена, а внутри церковь была изуродована многочисленными перегородками. Со временем здание церкви вследствие варварского использования начало постепенно разрушаться. Фундамент пришёл в негодность, связи нарушены, купол прогнил. В 1994 году Введенский храм был возвращён Православной Церкви, но до сих пор не может быть использован по назначению из-за крайне аварийного состояния. Были убраны только внутренние перегородки и расчищено от мусора пространство внутри храма. В 1996 году над храмом снова засиял крест.