С 1630 года Белый город был обнесён каменною стеною, а до этого был ограждён деревянным тыном из заострённых на конце и врытых в землю брёвен и назывался острогом. Этот острог был устроен в 1559 году присланным для строительства астраханского кремля дьяком Иваном Выродковым. Им же была построена и первая церковь в остроге, в честь Рождества Пресвятой Богородицы. Предположительное время её построения, 1560 год. Была она первоначально деревянною и однопрестольною.
Само построение этой церкви имело особые для того причины. Правивший в это время в Русском государстве царь Иоанн Васильевич Грозный, как и многие образованные люди на Руси, в первую очередь святой митрополит Московский Макарий, был убеждён, что Астрахань, это древняя Тмутаракань, один из уделов русских князей. Посылая русских ратников на покорение Астраханского ханства в 1556 году, царь Иоанн Грозный вспоминал, как древний и славный его предок святой князь Владимир Киевский, просветивший русскую землю святым крещением, раздавая области детям своим, эту Астрахань, именовавшуюся тогда Тмутаракань, дал сыну своему Мстиславу, который воздвиг здесь храм в честь Пречистой Богородицы. Помня об этом и давая наказ о строительстве города Астрахани дьяку Выродкову, царь повелел ему выстроить церковь в честь Рождества Пресвятой Богородицы, подобно той, что стояла в Тмутаракани. Этим закреплялась духовная преемственность прежней Тмутаракани, древнего удела русских князей и новоустроенной Астрахани.
Построенный храм первое время играл роль главного, соборного в городе, вплоть до 1568 года, когда прибывший в Астрахань игумен Кирилл строит в кремле новый соборный храм в честь Сретения Владимирской иконы Божией Матери. Рождество-Богородицкая церковь превращается в обычный приходской храм, прихожанами которого становятся в основном стрельцы. В 30-х годах XVII века в Белом городе были размещены конные стрельцы, это место стало называться Стрелецким городком, или Стрелецкой слободой или просто Слободой. К концу XVII века церковь сильно обветшала, в 1684 году была полностью перестроена по указанию самого Патриарха Иоакима, «Церковь Рождества Пресвятой Богородицы разобрать и прирубить к ней алтарь круглый тройной и верх на церкви сделать не шатровый, по чину прочих деревянных церквей».
После революционных событий 1917 года Рождество-Богородицкий храм два раза снова на краткое время становился соборным храмом города Астрахани. Первый раз с января по апрель 1918 года, когда после январских боёв вход в кремль и Успенский собор для верующих был закрыт. Второй раз после захвата собора обновленцами в 1923 году. Архиепископ Фаддей Успенский, приехавший в Астрахань в декабре этого года, сделал Рождество-Богородицкий храм своей кафедрой.
В феврале 1924 года обновленцы захватили нижний храм Рождество-Богородицкой церкви, в апреле в их руках оказался и верхний храм. В 1930-е годы местные власти отобрали храм у обновленцев. Рождество-Богородицкий храм состоял на учёте в Главнауке как памятник архитектуры, но это не смутило специально созданную комиссию, вынесшую 21 марта 1932 года ему приговор, «С учета Главнауки снять, так как астраханским представителем Главнауки брались на охрану все вообще старые церкви и монастыри города, не считаясь с отсутствием у некоторых художественно-исторической ценности». Храм решено было снести, так как в городе оставлялась одна барочной архитектуры церковь, Успенский собор и ему незачем иметь ещё одну барочную, Рождество-Богородицкую церковь». В заключении комиссии, решавшей судьбу церкви, было сказано, «что оставить её будет политическая ошибка». В том же году храм разобрали. Сейчас на этом месте, на перекрёстке современных улиц Советской и Коммунистической, находится сквер Пушкина.
