В 1950-х годах в районе железнодорожного вокзала Благовещенска было возведено одноэтажное деревянное здание, предназначенное для клуба железнодорожников. Вокруг клуба был разбит сквер, служивший местом отдыха для жителей города. Со временем, особенно к началу 2000-х годов, здание клуба пришло в запустение: были отключены тепло, электричество и водоснабжение, территория вокруг него заросла, а само строение оказалось заброшенным.
Летом 2012 года, по инициативе епископа Благовещенского и Тындинского Лукиана, руководство Российских железных дорог передало здание бывшего клуба и прилегающий участок земли Благовещенской епархии. Передача этого имущества стала важным шагом в деле возрождения духовной жизни в районе железнодорожного вокзала. Сразу после передачи начались работы по благоустройству территории: уборка мусора, расчистка сквера, ремонт и подготовка здания к богослужениям. В этих трудах активно участвовали прихожане и сестры епархиального женского монастыря в честь Албазинской иконы Божией Матери.
Решение о преобразовании бывшего клуба в православный храм было принято с учётом архитектурных особенностей здания, которое в плане напоминало утраченный Михаило-Архангельский храм. . Новый храм был посвящён святым мученицам II века — Вере, Надежде, Любови и матери их Софии.
30 сентября 2012 года, в день памяти святых мучениц, в новообразованном храме была совершена первая Божественная литургия. Богослужение возглавил епископ Лукиан в сослужении духовенства епархии. На службу был принесён чудотворный образ Албазинской иконы Божией Матери, перед которым молились многочисленные прихожане. Это событие ознаменовало начало полноценной духовной жизни прихода.
В ночь на 31 октября 2012 года произошло возгорание: неизвестные подожгли крест над входом в храм, и огонь перекинулся на крышу. Благодаря своевременному вмешательству сотрудника МЧС и оперативным действиям пожарных, возгорание было быстро ликвидировано, и храм не получил серьёзных повреждений. Этот инцидент не остановил восстановительные работы, и к январю 2013 года первый этап реконструкции был завершён. В праздник Рождества Христова храм официально открыл свои двери для прихожан.
Важным этапом в жизни прихода стало освящение и передача в дар тактильно-доступной иконы Божией Матери «Казанская» 30 сентября 2022 года. Эта икона, созданная в рамках проекта «Увидеть ИКОНУ», предназначена для людей с проблемами зрения, что подчёркивает стремление прихода к социальной инклюзии и заботе о всех категориях верующих.
