Деревянная Богоявленская церковь в Земляном городе построена в 1640-х годах, упоминается в 1648 и 1671 годах. Предположительно церковь сгорела. На её месте в 1697 году упоминается деревянная Петропавловская церковь. Храм находился в слободе Сияновой у Мочаговских ворот. К 1723 году деревянный храм сильно обветшал и церковный староста Михаил Иванович Сербин на свои средства начал строить другой, тоже деревянный. К 1730 году строительство храма завершено и в июле освящен архимандритом Спасского монастыря Иларионом, вместе с приделом. В 1749 году старую деревянную Петропавловскую церковь, которая по ветхости своей предназначалась в ломку, перенести в новообразовавшуюся слободу (об этой церкви дальше). При собранной старой церкви на новом месте построена новая деревянная колокольня, к трапезе, с южной стороны, пристроена придельная церковь в честь Святого Апостола Андрея Первозванного, покровителя русских моряков.

29 августа 1809 года архиепископом Гаием произведена закладка нового храма. Строилась церковь на пожертвования прихожан, а также на средства астраханского купца Алексея Ивановича Колпакова, пожертвовавшего на строительство 40 500 рублей. Сам Алексей Иванович в том же 1809 году скончался, а продолжил начатое им дело его сын Иван по духовному завещанию своего родителя. Храм построен в камне в 1814 году. 29 июня церковь освящена архиепископом Гаием. К храму пристроены два придела: правый в честь Апостола Андрея Первозванного, освященный ректором семинарии и архимандритом Спасского монастыря Дионисием 30 ноября 1814 года, левый в честь Святителя Алексия, митрополита Московского, небесного покровителя купца Алексея Колпакова, освященный 19 февраля 1815 года ключарём Кафедрального собора протоиереем Кириллом Васильевым. В августе 1867 года начались строительные работы. Боковые приделы вынесены из трапезы и поставлены на один уровень с главным алтарём. Трапеза расширена, купола и крыша храма покрыты железом и покрашены. На трапезе вместо черепичной устроена железная крыша, кресты на церкви и на колокольне переделаны и позлащены. Устроена ограда вокруг церкви из нового кирпича, на ней установлены чугунные решетки и чугунные ворота. Восстановленные боковые приделы освящены в честь Андрея Первозванного 16 июня 1868 года архиепископом Афанасием (Дроздовым), в честь Святителя Алексия Московского 15 июня 1869 года ректором семинарии архимандритом Александром.

Трёхъярусный резной деревянный иконостас вызолоченный на полимент, изготовлен священником Ильинской церкви Астрахани Иларионом Ивановым, установлен незадолго до освящения храма в 1814 году. Иконы писали и роспись храма делали астраханские мещане Василий Никитин, Василий Фёдорович Жуков, купеческий сын Назар Петрович Жуков и священник Михаило-Архангельской церкви Василий Андреев. Новые трёхъярусные иконостасы для придельных храмов изготовлены в 1842 и 1844 годах на средства купца Ивана Хлебникова и чиновников Петра и Гаврила Кузьминых. После перенесения приделов в августе 1867 года вместе с ними перенесены и иконостасы.

Святыни Храма: Евангелие 1648 года в бархатном красном переплёте, на верхней доске с серебряным распятием и серебряными изображениями четырёх евангелистов по углам. На Евангелии надпись: «Февраля 3 дня Государь, Царь и Великий князь Алексей Михайлович всея Руси пожаловал сию книгу – Евангелие в Астрахань в церковь Богоявления Господня, что в стрелецкой слободе Иванова приказа Баскакова, а надписал сию книгу Казанского дворца подьячий Трифон Щелоков»; Древний восьмиконечный серебряный крест 1636 года с надписью: «Сей крест дали вкладу святых апостолов Петра и Павла, что за Москвою-рекою за Калужские ворота стрельцов пятьсот человек по своих родителях»; Две иконы: Божией Матери «Достойно есть» и великомученика Пантелеймона-исцелителя, написанные на святой горе Афон в Русском Пантелеймонове монастыре в 1872 году, на средства ктитора церкви В.Г. Соколова.

В 1930 году после ареста Астраханского епископа Филиппа (Ставицкого) церковь занята обнавленцами. В 1934 году советские власти окончательно закрыли храм. В 1935 году храм разрушен для рыбзавода на щебёнку и кирпичи. Кирпич и щебень несколько лет лежали неубранными.

Храм Петра и Павла находился между площадь Шаумяна домом 11 и домом 24 (дом Ивановой) на месте детской, баскетбольной площадок, дороги и дома 3.