Благословом Његовог Преосвештенства Епископа нишког Г. Г. Иринеја 03.априла 1999. године, на Лазареву суботу, постављен је у Парку Светог Саве у присуству свештенства, монаштва и верног народа града Ниша и околине, камен темељац за изградњу Храма св. цара Константина и царице Јелене, у тешко време за Србију-време НАТО бомбардовања (24. март-10. јун 1999. године)
Градња Храма је започета у време градоначелника Ниша господина Зорана Живковића и председника скупштине града Ниша господина Бранислава Јовановића.
За градњу Храма ангажовани су:
Пројектант: архитекта господин Јован Мандић, и архитекта госпођа Јелена Мандић
Извођач радова: Грађевинар Ниш
Инввеститор: Град Ниш
Посредник између извођача радова и епископа: јереј Љубиша Марковић
Надзор: господин Борислав Михаиловић и господин Бобан Милосављевић
У темељ храма, уз три камена темељца, постављена је боца са повељом и све скупа заливено бетоном. На том мету постављен је Крст.
Са почетком ископавања крипте Храма Крст је измештен поред градилишта и постао је место окупљања верног народа ради молитве.
Убрзо је саграђена капелица у којој је отац Љубиша Марковић организовао редовно дежурство. Од 2000. године отац Љубиша редовно, у овој капелици, чита акaтист недељом у поподневним часовима, где се окупљао већи број верног народа.
Израђена је нова капелица са вратима која су се закључавала. Постављене су и иконе и горионик за свеће.
3. јуна 2001. године испред капелице, где ће се изградити наш Храм, пресечен је славски колач. У тадашњој Скупштини Града Ниша је први пут прослаљена слава св. цара Константина и царице Јелене, и од тада Град Ниш слави нашу храмовну славу као славу Града Ниша.
2001. год. догодило се велико искушење за наш Град. Октобра је у пламену изгорела Саборна црква у Нишу, Крст испред нашег будућег храма је поломљен а уочи Ваведења исте године и капелица је изгорела у пожару.
3. јуна 2002. Град Ниш почиње вишедневно славље Крсне славе Града Ниша која се поред центалне прославе, Свете Литургије и литије на сам дан славе, обележава и драмским, музичким и спортским догађајима.
12. септембра 2002. године тадашњи Епископ нишки Г.Г. Иринеј, а сада Патријарх српски, извршио је освећење крстова, и извршено је подизање на новосаграђени наш Храм у присуству многобројног свештенства, монаштва и верног народа Ниша и околине. Дародавац крстова био је господин +Милић Радовановић (Биотехна Ниш).
Уочи Божића 2003. године у присуству великог броја верујућег народа први пут је извршено освећење и паљење бадњака испред нашег Храма. Те исте године први пут је извршено и освећење Богојављљенске водице.
Након четири година од утемељења градске славе први пут је у званични програм прославе ушла је и једна изложба уметничких дела. Чланови мултимедијалног Удружења „Цар Константин“ приредили су изложбу акварела, уља на платну, акрила икона и скулптура инспирисаних углавном мотивима Византије. Резањем славског колача изложбу је у крипти нашег Храма отворио тадашњи владика нишки Иринеј. Изложба је била и продајног карактера а део новца намењен је као донација изградњи Храма.
Уочи градске славе 2005. године уз присуство великог броја грађана и личности из јавног градског живота и многобројним гостима из иностранства изведен је богат музичко сценски програм. На коме је између осталих учествовао и тада недавно основани Црквено играчки ансамбл „Бранко“ из Ниша.
3.јуна 2005. Након Свете Литургије на којој је началствовао тадашњи епископ нишки Г. Г. Иринеј у присуству великог броја верујућег народа и многобројних представника власти града Ниша, као и представника из иностранства, а након резања славског колача, пошло се у Литију на којој су се први пут по благослову владике огласила Звона из нашег Храма. Дародавац звона био је господин Властимир Николић-Лале Пећарац-који је био и колачар и домаћин славе за ову 2005 годину.
Почетком октобра 2005. по благослову Епископа нишког Иринеја формира се прво црквено братство при начем Храму. На дан Зачећа светог Јована Крститеља 6. октобра, братсво Храма на челу са тадашњим старешином Храма јерејем Љубишом Марковићем заједно служи прву Свету Литургију. Од тог дана, наш Храм поред своје Храмовне славе слави и празник Зачећа светог Јована Крститеља.
Прво крштење у нашем Храму обављено је 9. октобра 2005. године.
Прво венчање у нашем Храму обављено је 15. октобра 2005. године.
Прво братство Храма (октобра 2005.) чинили су:
+протојереј Душан Стевановић, тада парох први (упокојио се 2007.)
јереј Љубиша Марковић-старешина Храма, тада парох други
јереј Милан Драговић, тада парох трећи
јереј Дејан Јовановић, тада парох четврти
На дан Ваведења Пресвете Богородице 4. децембра 2006. Храм добија и првог ђакона. Нови сабрат Храма постаје и ђакон Бобан Миловановић.
3. Септембра 2007. на новоформирану трећу парохију владика нишки Иринеј поставља протонамесника Дејана Бараћа (који је претходно био парох орљански).
1. августа 2008. на упражњену прву парохију долази протојереј-ставрофор Милан Кртстић (који је претходно био парох у Виндзору и клирик Епархије америчко-канадске).
Децембра исте године на дан Ваведења Пресвете Богородице, наш Храм добија и другог ђакона. Епископ нишки за ђакона поставља Дејана Арсића-вероучитеља из Ниша.
16. фебруара 2009. год. тадашњи епископ Нишки Иринеј за старешину Храма св. цара Константина и царице Јелене у Нишу поставља протојереја-ставрофора Милана Крстића.
Тако да братство Храма марта 2009. године чине:
протојереј-ставрофор Милан Кртстић, парох први
јереј Љубиша Марковић, парох други
протонамесник Дејан Бараћ, парох трећи
јереј Милан Драговић, парох четврти
јереј Дејан Јовановић, парох пети
ђакон Бобан Миловановић и
ђакон Дејаљ Арсић
Првог Јануара 2011. године братсво Храма добија новог сабрата протонамесника Малишу Миловановића дотадашњег пароха при Храму св. оца Николаја.
Отац Малиша постаје шести парох при нашем Храму.
8. Августа 2011. Епархија нишка добија новог Епископа. На место нишких Епископа одлуком Светог Архијерејског Сабора Српске Православне Цркве долази епископ др. Јован Пурић.
Почетком новембра 2011. по благослову Епископа нишког Г.Г. др Јована нови сабрат Храма постаје јереј Александар Ђорђев службеник Епархијског Управног Одбора.
Јереј Дејан Јовановић по благослову нашег владике одлази на службу на парохију при Саборном Храму у Нишу. А на његово место долази протонамесник Предраг Радосављевић до тада парох Рутевачи у алексиначком архијерејском намесништву.
7. Новембра 2011. Отац Предраг прима пету нишку парохију при нашем Храму.
18. Децембра 2011. наш владика Јован рукополаже ђакона Бобана Миловановића у чин Презвитера. Отац Бобан добија на службу новоосновану осму нишку парохију при нашем Храму.
1. јануара 2012. ђакон Дејан Арсић постаје парохијски ђакон.
Крајем децембра 2011. наш Храм добија новог ђакона- Горана Вучковића –вероучитеља из Ниша.
Почетком фебруара 2011. после одласка оца Малише на службу у Винипег-Канада, постаје упражњена шеста парохија. На место пароха шестог долази отац Александар и наш нови сабрат јереј Борислав Стаменковић, који ће заједно опслуживати шесту нишку парохију.
Благословом Епископа Нишког Г. Г. др Јована за помоћник старешине нашег Храма постаје јереј Милан Драговић 8. фебруара 2011.
11. јуна 2012. Ђакон Живко Миловић, катихета и парохијски ђакон при Храму св. Николе, постаје наш сабрат.
Прота Милан Крстић крајем јуна 2012. Одлази на нову парохијску дужност у Мидлтон-САД.
31. јула. 2012. Владика нишки поставља протојереја Небојшу Оровића за старешину храма и пароха првог.
1. септембра 2012. На упражњену седму парохију долази јереј Саво Крчо из Републике Српске.