Торжественная закладка храма была произведена 23 ноября 1902 года, а первый камень, положенный в основание, был освящён 6 декабря того же года. Строительство храма продолжалось до 1905 года и осуществлялось на средства военного ведомства Туркестанского края, городского бюджета и частных пожертвований. Наиболее крупный вклад внёс коммерческий советник Николай Иванович Иванов, на чьи средства был сооружён деревянный, изысканной работы, золочёный иконостас. Проект церкви принадлежит инженеру Александру Александровичу Бурмейстеру, а строительством руководил военный инженер капитан Фёдор Смирнов.
Архитектурное решение храма выполнено в традиционном русском стиле, характерном для православных храмов того времени. Здание кирпичное, с элементами эклектики, что отражает распространённые архитектурные тенденции начала XX века. Храм имеет центральный купол и колокольню. Внутри храм был отштукатурен ганчем и выкрашен в бирюзовый цвет, а потолки покрашены белым цветом. Полы были из цементных плиток, в алтаре — пол деревянный, окрашенный масляной серой краской. Солия деревянная, также выкрашена в серый цвет. У западной стены храма над входными дверями устроены хоры для певчих. По переднему фасаду здания с двух сторон пристроены две башенки для колоколов. Для храма были отлиты три колокола, общим весом 0,25 тонн, самый большой из которых весил 12 пудов.
В 1920-х годах храм был захвачен обновленцами, христианским движением, появившимся после Февральской революции 1917 года. Православные прихожане проводили богослужения около часовни в честь иконы Божией Матери «Всех скорбящих Радость». После Великой Отечественной войны храм был возвращён православной церкви. Во время землетрясения 1966 года и последующего пожара храм пострадал, после чего были проведены первые реставрационные работы. Весной 1996 года реставрации подверглись могилы святителей на Боткинском кладбище.
Последние и самые масштабные работы по реставрации храма Александра Невского проводились с 2011 по 2014 годы. За это время был облагорожен фасад храма и его внешний периметр. Сгладили неровности кирпичной кладки, покрасили купола, фасадные иконы храма поместили под стеклопакеты. Укрепили несущие стены и проёмы металлическими конструкциями, реконструировали балкон для хора. Утеплили пол и поменяли электропроводку, добавили искусственное освещение под потолком.
