Первой кирпичной церковью города стала Покрово-Инокентие-Николаевская церковь.Причем,онастала и первым кирпичным зданием города. До нее даже каменный фундамент под деревянные здания боялись подводить, не говоря уже о строительстве кирпичных зданий. Покрово-Иннокентие-Николаевскую церковь так же предполагалось строить из дерева. Но Преосвященный Мартиниан настоял на том, чтобы построить кирпичную. Место под нее отвели недалеко от Николаевского храма (находился на углу улиц Релочной и Никольской) по улице Никольской (ныне - Комсомольская).
Первый каменный храм, как и первый деревянный, во многом обязаны своим существованием Александру Поликарповичу Сизому. Известно, когда Преосвященный Якутский Дионисий, знавший о. Александра еще по службе в Якутске, пригласил его на место настоятеля Кафедрального собора в Якутск, то отец Александр после долгих колебаний согласился. Решающую роль в принятии им именно такого решения сыграло безразличное отношение прихожан Николаевского прихода к строительству нового, более обширного храма. Это касалось и жителей всего города, так как на 6080 человек в 1878 году приходилось три небольших деревянных храма, уже тогда не вмещавших всех желающих. Но любовь и уважение горожан к о. Александру были слишком велики, чтобы допустить такое легкое расставание с ним. Представители горожан во главе с военным губернатором пришли к нему с просьбой изменить свое решение и остаться в городе Благовещенске. Отец Александр поставил единственное условие благовещенское общество должно было дать обещание «путем добровольных пожертвований и раздачею подписных листов построить новый, обширный храм вместо тесного, неуютного Николаевского». Здесь же сразу было собрано около 1 тыс. рублей. Но впоследствии ему не раз приходилось с низкими поклонами просить пожертвования «не только у зажиточных горожан и вообще у прихожан, но и у приисковых рабочих, стоя по несколько часов с непокрытой головой в разрезах».
29 апреля 1879 года была совершена литургия в Николаевской церкви Благовещенска. Затем епископ Мартиниан заложил трехпрестольный приходский храм. Главный престол храма посвятили празднику Покрова Пресвятой Богородицы. Епископу сослужили при этом ректор благовещенской семинарии архимандрит Иаков, отцы протоиереи Кафедрального собора Павел Политов и Николаевского храма - Александр Сизой, священники Афанасий Шастин, Игнатий Черных, Алексей Политов. На закладке присутствовал губернатор Амурской области барон Офенберг.
Строительство начиналось при наличии церковного капитала в 4 тысячи рублей, 15 тысяч было выделено из средств Священного Синода. За последующие три года он был полностью построен, оставалось только построить колокольню, покрыть храм железом, закончить внутренние работы (пол, иконостас), что предполагалось сделать летом 1883 года. По смете, составленной местным архитектором, стоимость храма составляла 140 тысяч рублей. Деньги эти были собраны преимущественно благодаря личным пожертвованиям. Так, в 1880 году жители г. Иркутска Яков Андреевич Немчинов, коммерции советник, и Иван Иванович Базанов, действительный статский советник, пожертвовали на его строительство: первый 2, второй - 1 тысячу рублей. Летом 1882 года, когда все средства были исчерпаны, почетная потомственная гражданка г. Иркутска Александра Никаноровна Портнова пожертвовала 5 тысяч рублей облигациями 2-го восточного займа. Храм стал самым обширным и вместительным в городе «в длину около 20 саженей, не считая осьмерика, и столько же в ширину, с колокольней в 20 саженей».
Позже освятили приделы храма: в честь святителя Николая Мирликийского в 1886 году, в честь святителя Иннокентия Иркутского, Чудотворца в 1887 году.
В 1897 году почетный потомственный гражданин Николай Васильевич Ельцов пожертвовал церкви колокол весом 227 пудов.
Шиндялов Н.А. История Благовещенска. 1856-1907. Очерки, документы, материалы/ Серия «Благовещенск. Из века в век». Благовещенск: ОАО «Амурская ярмарка», 2006