Греки, переселившiеся въ Таганрогъ изъ Керчи, не знали русскаго языка, также точно не знали его и вновь переселявшiеся греки изъ Константинополя и съ острововъ Архипелага, а потому крайне нуждались въ священнике, который зналъ бы греческiй языкъ. Въ виду этого въ семидесятыхъ годахъ прошлаго столетiя и былъ присланъ имъ изъ Константинополя греческiй iеромонахъ Герасимъ Белутъ, которому разрешено было совершать богослуженiе въ Архангело-Михайловской церкви поочередно съ русскими священниками. Но этой, прибывшiй изъ Константинополя ихъ соотечеcтвенникъ грекамъ чемъ то не угодилъ, почему они и просили архiепископа Евгенiя Славенскаго, когда онъ былъ въ Таганроге въ 1778 году, чтобы онъ назначилъ имъ другого, именно iеромонаха Епифанiя: согласившись на ихъ просьбу, архiепископъ вместе съ темъ советовалъ имъ устроить свою собственную церковь, Греки, составлявшее въ то время уже значительное населенiе, приняли близко къ сердцу советь Евгенiя и занялись этимъ вопросомъ. Они избрали изъ своей среды Георгiя Трандафилова, Дмитрiя Панiатора, Георгiя Гуннiя, Анастасiя Воспоря, Дмитрiя Паламарина, Емануила Кацинахина, Георгiя Економа, Панагiота Смирила, Георгiя Кранеота, Iоанна Россетiя и Панагiота Аслана, которые и вошли съ ходатайствомъ въ 1780 году предъ apxiепископомъ Славенскимъ Никифоромъ о разрешенiи имъ построить церковь во имя царей Константина и Елены, а такъ какъ они иностранцы и русскаго языка не знаютъ, то съ правомъ совершать богослуженiе на еллинскомъ языке, и что для таковой цели избрана коммиссия, собраны деньги 1000 руб. и приготовленъ матерiалъ, а для обезпеченiя причта они установили особый сборъ съ весовъ и меръ. Въ составъ коммиссiи по построенiю церкви вошли наиболее уважаемая лица греческаго общества, именно: Паламарь, Каницiоти Ганала, Пагонатъ, Гавала, Елинъ и Христодулы. Постройка съ разрешения епархiальнаго начальства началась въ 1781 году и въ следующемъ была окончена и 13-го марта освящена; епископомъ Неофитомъ. Для священнодействiя въ ней греки пригласили съ острова Пароса протопопа Никиту Агуроса, который, прослуживъ два года въ Таганроге, уехалъ на родину; вообще приглашенные изъ заграницы греческiе священники и монахи, какъ тогда, такъ и потомъ не ладили съ своими таганрогскими прихожанами. Тогда греки выбрали светскаго человека Константина Павловича Схоларiуса и просили Полтавское епархiальное начальство, къ которому приписана была церковь, рукоположить, на что последовало соглаciе.
Въ это же время проживалъ по какому то случаю въ Таганроге епископъ Феодосiйскiй и Марiупольск1й Дорофей Возмуйловъ, рукоположенный въ архiереи изъ архимандритовъ Неулискаго монастыря св. Благовещенiя, онъ и умеръ въ Таганроге въ 1790 году 10 сентября.
Между темъ деревянная церковь, къ тому же построенная на скорую руку, приходила въ ветхость. Въ виду этого Иванъ Андреевичъ Варвацiй обратился къ городскому обществу съ предложенiемъ соорудить каменную церковь, а деревянную снести. Но строительный комитетъ отклонилъ отъ себя исполнение предложения Варвацiя, предлагая обратиться съ этимъ къ духовному начальству, такъ какъ его предложенiе связано съ сносомъ уже существующей церкви; это было въ 1809 году; тогда Варвацiй, боясь безконечныхъ проволочекъ по тогдашнимъ учрежденiямъ, а въ особенности консисторiямъ, отказался отъ этой мысли, а избралъ другое место для постройки церкви, где ныне Iерусалимскiй монастырь. По некоторымъ другимъ сведенiямъ Варвацiй предложилъ построить церковь съ темъ, чтобы она оставалась его собственностью, на что греки, разумеется, не согласились.
Церковь же темъ не менее требовала исправленiя, съ каковою целью въ томъ же 1809 году было избрано десять ктитарей, которые и занялись собиранiемъ средствъ для сооруженiя каменной двухъ-престольной церкви.
После продолжительныхъ трудовъ храмъ былъ выстроенъ въ такомъ виде, каковъ онъ теперь. Постройка фундаментальная и грацiозная. Старая же деревянная церковь была продана на сносъ крестьянамъ Бахмутскаго уезда, Ясиноватой волости села Михайловки въ 1830 году, где потомъ сгорела. Богослуженiе въ этой церкви совершалось не на одномъ греческомъ языке, но и на русскомъ въ виду постоянно нароставшаго русскаго населенiя.
При церкви была некогда певческая школа, помещавшаяся въ соседнемъ именiи, принадлежавшемъ церкви, но въ настоящее время этой школы нетъ, многiе певчiе и регенты таганрогскихъ церковныхъ хоровъ обучались тамъ церковному пенiю.