Введенская церковь, достоявшая до наших дней, хоть и в очень искаженном виде, располагается недалеко от древнего Иоанно-Предтеченского монастыря. В Солдатской слободе, с благословения архиепископа Платона Любарского, была построена деревянная церковь в честь Введения во храм Пресвятой Богородицы. Освящёна она была 21 ноября 1797 года самим архиепископом Платоном. Новоустроенная церковь была снабжена церковной утварью: частью оставшейся от упразднённой Никольской церкви, а частью, от Троицкого монастыря. В 1814 году в фундаменте церкви были обнаружены подгнившие венцы, отчего она оказалась непрочной и склонной к разрушению. Вследствие этого благочинный протоиерей Андрей Бедняков и церковный староста купец Николай Шайкин 7 июля 1814 года обратились к Астраханскому архиепископу Гаию Токаову с просьбой выдать им сборную книгу на построение нового каменного Введенского храма. 30 июня 1817 года тем же лицам была выдана храмоздательная грамота.
4 сентября 1818 года было заложено основание храма. Основные строительные работы вёл астраханский подрядчик Филипп Петров, а главным жертвователем на строительство храма стал астраханский купец Иван Львович Михайловский. После построения каменной трапезы в ней были устроены два боковых придела, которые были освящены, правый в честь равноапостольных Константина и Елены 16 января 1819 года протоиереем Фёдором Александровым, а левый в честь Благоверного князя Александра Невского 19 января им же. Сам храм был закончен постройкою в 1822 году и освящён Астраханским архиепископом Авраамом Шумилиным 14 мая.
В 1872 году к колокольне Введенского храма с левой стороны была пристроена каменная палата для церковной ризницы. В 1902-1903 годах расширена была трапеза храма с обеих сторон, с перенесением обоих придельных алтарей на один уровень с центральным. Боковые приделы были освящены, правый в честь Фёдоровской иконы Божией Матери, а левый в честь Равноапостольных царей Константина и Елены. Введенский храм был построен по одному архитектурному плану с храмом Иоанна Златоуста, но многочисленные перестройки со временем сильно изменили первоначальный облик церквей.
Введенский храм архитектуры классической с двухъярусной колокольней в одной связи. Расписан он был в 1821 году иконописцем Авакимом с товарищами. В 1903 году на расширенной части храм был заново расписан с подновлением прежней росписи. В 1912 году был сооружён новый центральный иконостас из фарфора, покрытый розовой и голубой эмалью с позолотой.
В 1923 году Введенский храм был захвачен обновленцами и находился в их ведении до 1939 года. После своего закрытия Введенский храм был передан автошколе на арендных основаниях. 11 августа 1953 года Астраханский облисполком своим решением постановил полностью переоборудовать церковное здание под автошколу «Глававтотранскадры». В результате этого переоборудования колокольня храма была снесена, а внутри церковь была изуродована многочисленными перегородками. Со временем здание церкви вследствие варварского использования начало постепенно разрушаться. Фундамент пришёл в негодность, связи нарушены, купол прогнил.
В 1994 году Введенский храм был возвращён Православной Церкви, но до сих пор не может быть использован по назначению из-за крайне аварийного состояния. Были убраны только внутренние перегородки и расчищено от мусора пространство внутри храма. В 1996 году над храмом снова засиял крест.
