В 1805 году, после закладки Вознесенского собора, епископом Воронежским и Черкасским Арсением было освящено место под строительство новой Александро-Невской церкви. Однако из-за изменения места под строительство потребовалось повторное освящение, которое провел священник Василий Рубашкин. Первоначально церковь была деревянной и возводилась по проекту архитектора Лавопиера. 29 июня 1810 года протоиерей Алексей Оридовский освятил построенную деревянную церковь в честь святого благоверного князя Александра Невского.
В 1822 году к церкви был пристроен придел во имя святой великомученицы Параскевы Пятницы, освященный 26 октября того же года протоиереем Иаковом Мерхалевым. В 1827 году войсковой атаман Д. Е. Кутейников предложил заменить деревянную церковь каменной. Предложение было поддержано, и был составлен план со сметой, одобренные в 1829 году императором Николаем I с повелением начать строительство каменного храма после завершения строительства Войскового Вознесенского собора в Новочеркасске.
В 1834 году была построена новая колокольня, а в 1835 году перестроена сама церковь: сооружен каменный фундамент и добавлен второй придельный алтарь. В 1866 году деревянную кровлю церкви заменили на железную. Однако строительство каменной церкви затянулось. В 1889 году был составлен новый проект каменного храма по образцу церкви в имении Ф. Я. Терещенко около Киева. Проект был утвержден войсковым наказным атаманом князем Н. И. Святополк-Мирским и получил благословение архиепископа Макария.
Строительство нового храма началось в 1891 году. К 1893 году основные строительные работы были завершены, и летом 1894 года на главный купол храма был установлен крест. Мраморный иконостас был заказан церковным старостой А. Абрамовым в Москве у мастера Кутырина за 22 тысячи рублей и установлен летом 1896 года. Правый придел церкви был устроен в честь святой великомученицы Параскевы Пятницы и освящен 19 октября 1897 года с благословения архиепископа Афанасия. В 1899 году храм был окрашен внутри масляной краской и украшен стеновой живописью, выполненной художником Гордиенко.
Новый Александро-Невский храм был построен в неовизантийском стиле, с полукруглой апсидой в алтаре, за которой было устроено помещение для ризницы. Храм вмещал до 1500 человек. К Александро-Невской церкви были приписаны: каменная Александро-Невская часовня (1882), не сохранившаяся; церковь в лагере Донской артиллерии (1897); часовня, построенная напротив здания Новочеркасской почтовой конторы (ныне Узел связи на Платовском проспекте).
