В 50-х годах ХIХ века в Новочеркасске в период управления Войскового Наказного Атамана М.Г. Хомутова стала пробиваться инициатива о строительстве церкви во имя великомученика Георгия Победоносца на Колодезной площади. Но казаки особого «рабочего полка», ведущего строительные и ремонтные работы в Новочеркасске настояли на том, чтобы церковь строилась именно на их территории, т.е. на Сенной площади, взамен ветхой полковой часовни. Местные власти пошли навстречу «качурам» (так называли в народе казаков этого рабочего полка). И в 1864 г. деревянная Константино-Еленинская церковь была установлена на Сенной площади рядом с казармами «рабочего полка».
По некоторым преданиям и письменным свидетельствам материал для деревянного храма святых равноапостольных Константина и Елены, а также колокольни был взят из разобранных ранее деревянной Троицкой церкви и деревянного кладбищенского Димитриевского храма.
Но так как эта церковь изначально не являлась новой, то, естественно, что она вскоре стала ветхой и потребовалась ее замена. Прихожане этого района в начале ХХ века стали активно собирать средства на постройку новой каменной церкви и избрали специальный попечительский совет, которому поручили принять меры к построению нового Константино-Еленинского храма. Председателем попечительского совета избрали А.И. Сюсюкина.
16 октября 1903 года попечительский совет приступил к работе. Он организовал сбор необходимых средств как от прихожан Константино-Еленинского прихода, так и от посторонних лиц. Активная работа попечительского совета была крайне осложнена войной России с Японией в 1904-1905г., в которой участвовали и Донские казаки. Военное время потребовало дополнительных расходов и сбор средств в пользу строительства новой каменной церкви оказался затруднен. Место под строительство каменной Константино-Еленинской церкви освятили 5 марта 1906 г. («Донские Епархиальные Ведомости», 1906 г., © 8, неоф. отд. с. 224)
Подряд на строительство кирпичной церкви во имя святых равноапостольных Константина и Елены заключили с крестьяниным С. Павловым и мещанином Хоплановым. Скудость собранных средств подталкивала попечительский совет находить нестандартные решения. Например, оплата подрядчикам производилась не за весь комплекс выполненных работ, а по мере выполнения работ и с одобрения попечительского совета, а также городского архитектора, автора проекта храма В.Н. Куликова. Экономили на всем. Так, из 796 тыс. штук кирпича, уложенных в новый храм куплено было 723.225 штук, уложено старого кирпича, полученного при разборке старой каменной ограды — 32.800 шт. Пожертвовано храму натурным кирпичом 39.975штук. Торговались с каменщиками, с продавцами железных балок и рельс для перекрытий. «И так во всех расходах до мелочей соблюдалась во всем экономия».(«Донские Епархиальные Ведомости». 1906 г., с. 898.).Всего на постройку храма (вчерне, без отделки) затратили 15 тыс.648руб.35коп. Колориферную печь для обогрева храма в зимнее время изготовил мастер печных работ крестьянин Т. Сундуков. Двойные железные оконные рамы по рисунку городского архитектора В.Н. Куликова изготовили на Новочеркасском заводе Миненкова. К осени 1906 г. новый каменный Константино-Еленинский храм вчерне окончили. (отчет в «Донских Областных Ведомостях», © 221 за 1906 г.).
Но освящен Константино-Еленинский храм только 10 мая 1909 г. кафедральным протоиереем Василием Петровым. В нем устроили три престола: во имя Духа Святого и два придельных. Левый во имя Равноапостольного Константина и его матери Елены: а правый — во имя Святого Николая Мир-Ликийского, чудотворца. Задержки со сроками ввода в строй нового храма объясняются нехваткой средств на отделку, роспись церкви, а также на изготовление необходимой утвари. Храм построен в старорусском стиле. Квадратная церковь соединена с высокой каменной колокольней. Многие иконы в храме написаны Донским иконописцем М. Волковым.
Судя по Акту обследования от 3 мая 1933 г. Константиновская церковь (именно так она именуется в документе — Е.К;) уже называлась «бывшая», а значит не действующая. Когда ее конкретно закрыли нам неизвестно. Но нам известно, что после оккупации и освобождения Новочеркасска церковь действовала. Есть косвенное указание и на то, что церковь в начале 1961 г. еще действовала, ибо в письме зав. горфинотделом И. Морозова начальнику бюро технической инвентаризации Горкомхоза Глушко от 23 февраля 1961 г. указано, что в городе действуют такие храмы как: Вознесенский собор, Константиновская, Георгиевская, кладбищенская и Михайловская церкви.
В 70-е, 80-е и 90-е годы Константино-Еленинская церковь работала. В начале 90-х годов на храме позолотили кресты и под ними маковки. Ныне в храме двухъярусный иконостас. Во время богослужений поют два профессиональных церковных хора. Настоятелем Константино-Еленинского храма в 1998 году служил протоиерей Александр Осяк.
Постановлением мэра г.Новочеркасска © 166 от 4 февраля 1997г. «О регистрации права собственности на недвижимое имущество за приходами Русской Православной Церкви Ростовской на Дону епархии Московской Патриархии» здание церкви Константина и Елены на Сенная © 5 было закреплено за приходом этого храма.
