В конце 1990 г. Алтайским благочинием при сотрудничестве «Главархитектуры» был объявлен конкурс на лучшее место для строительства нового храма. Выбор пал на территорию парковой зоны на пересечении трех районов. 11 мая 1991 г.
Святейшим патриархом Московским и всея Руси Алексием II был освящен закладной камень на строительство Собора Александра Невского. Первая Божественная Литургия была отслужена 12 сентября 1993 года, в престольный праздник будущего собора – день памяти святого благоверного князя Александра Невского.
С 20 августа 1993 года строительство не прекращалось ни на один день. Благодаря финансовой поддержке Покровского собора, трудами прихожан крестильный храм Александро-Невского собора был освящен 29-го января 1995 года Преосвященнейшим Антонием, епископом Барнаульским и Алтайским, в честь Богоявления Господня. Для города это очень знаменательное событие, так как Богоявленский храм это первый православный храм, построенный в Барнауле с 1917 года.