Разположена е в Стария град, на прехода между Хълма на играчите и Хълма на стражите, точно до източната порта на античния акропол.
Построена е през 1832 година на мястото на старата църкви и е богато украсена с икони на Захарий Зограф, Димитър Зограф, Атанас Гюдженов, Никола Одринчанин, Станислав Доспевски, Иван Пашкула.
Християнството навлиза във Филипопол още през IV век сл. Хр., а гражданите му вдигнали храм (на мястото, където сега е църквата) скоро след съдбовния Милански едикт (313 г.), с който император Константин Велики (306-337) признал Христовото учение за официална религия. Храмът бил посветен на самия римски император (Свети Константин) и на майка му (Света Елена). Изборът на мястото за храма не бил случаен. През езическата епоха, по време на гоненията на християни в дните на император Диоклециан (284-305) заловили 38 равноапостоли от Пловдив и околността, като между тях били и знатните граждани Севериан и Мемнос. Посечени били точно на мястото, където впоследствие е издигната черквата.
Според свидетелството на Теофан Изповедник храмът е въздигнат през 326 г., а според професор Козма Апостолидис първоначално се е наричал „Св. св. Севериан и Мемнос” и едва век по-късно е наименуван на канонизирания римски император и майка му. Протестантският богослов и пътешественик Стефан Герлах описва църквата като най-тайнствената в Пловдив през годините около 1578 г. Три века по-късно, към 1830 г. Константин Моравенов видял постройката в руини, без покрив. Преживяла превратностите на времето в продължение на хилядолетие и половина, през същинския османски период църквата била почти изоставена. Поради обезлюдяването на Трихълмието през XVIII век, в нея рядко се провеждало богослужение, а и неудобното ѝ местоположение затруднявало достъпа на черкуващите се християни.
Нововъздигнатият храм през 1832 година имал в амвона си иконите на светите Константин и Елена, изработени през XV век, а в подземието, където била костницата, била поставена старинна храмова апсида с древен християнски стенопис от IV-V век.