Още по време на Руско-турската освободителна война (1877-1878 г.) много българи започнали да напускат масово османската столица. След подписването на Санстефанския мирен договор (3 март 1878 г.) и последвалия го Берлински конгрес (юни 1878 г.) потокът на изселниците се засилил. Напускали преди всичко търговците, богатите занаятчии и най-вече интелигенцията. Останали предимно македонските българи, тъй като родните им места не били освободени и пак се намирали в пределите на Османската империя. Според една официална турска статистика през 1885 г. Цариград имал население от 1 милион и 33 хиляди жители, от които 384 910 турци, 156 032 арменци, 152 741 гърци, 44 377 българи и пр.
Положението на Българската екзархия, чието седалище бил Цариград, оставало неизяснено. Вторият български екзарх Йосиф Първи (1840-1915), който встъпил на екзархийския трон през април 1877 г., се намирал в доста затруднена ситуация. Той бил лишен от подкрепата на своите архиереи, които заминали за епархиите си; останал без доходи, тъй като владичина по време на войната не била събирана; нямал възможност да поддържа връзка с дейците от освободените български земи и затова решил да отиде временно в Пловдив, където по това време заседавала Европейската комисия по уредбата на Източна Румелия.
За Пловдив Йосиф Първи заминал на 1 юни 1878 г., като за свой заместник в Цариград оставил архим. Теодосий (по-късно Скопски митрополит) с един съвет от шестима мирски лица. Еврейската къща в „Ортакьой“, където се помещавала Екзархията, била освободена и архивата била пренесена в Метоха във „Фенер“. Там архим. Теодосий стоял до окончателното връщане на екзарха на 10 януари 1880 г. След дълги спорове в Пловдив, къде да бъде занапред седалището на Българската екзархия, надделяло мнението на опитния дипломат екзарх Йосиф Първи за Цариград, понеже само оттам той щял да поддържа своевременни и преки връзки с поробеното население от Македония и Одринска Тракия, пазейки го от произволите на властта и от покушенията на чужди народностни или верски пропаганди.
Този път за седалище на Екзархията била взета под наем една арменска къща в „Ортакьой“, която по-късно била закупена. Екзарх Йосиф проявил изключителни грижи за своите пасоми във вилаетите, но обръщал сериозно внимание и върху представителността на самата Екзархия в Цариград. Старата „Дървена църква“ била толкова пропаднала, че вече се страхували да служат в нея. Със съгласието на българското правителство, което финансово издържало Екзархията в пределите на Османската империя, било решено да се построи най-сетне нова и представителна църква.
За целта на 1 март 1888 г. бил изготвен специален правилник за провеждането на архитектурен конкурс за направата на нова църква. Той бил спечелен от амбициозния архитект Ховсеп Азнавур (1854-1935), арменец, английски поданик, живеещ и работещ в османската столица. Същият още през есента на 1888 г. започнал да разчиства старите и напукани основи, градени през есента и началото на зимата на 1859 г. в двора на „Дървената църква“. През март 1889 г. от страна на българското Министерство на външните работи и изповеданията била назначена строителна комисия по постройката на храма. Неин председател бил екзарх Йосиф, но на практика заместван от посочен негов заместник: бившия Скопски митрополит Теодосий (от 19 март 1889 г. до 11 януари 1890 г.); ик. Георги Хаджитилев, протосингел на Екзархията (от 13 януари 1890 г. до 1895 г.); бившия Скопски митрополит Максим (1895-1897) и Димитър Мишев, главен секретар на Екзархията (1897-1900). Останалите членове на комисията били Атанас Трайков, Никола Минчов, Атанас Калчов, Стоян Хр. Тъпчилещов, Христо Н. Бракалов и Христо п. Стаматов.
Междувременно на 25 юни 1890 г. бил издаден височайши султански ферман, с който се разрешавало на Българската екзархия да построи на мястото на старата „Дървена църква“ нова. По настояване на компетентни лица строителната комисия се разпоредила да започне цялостно разчистване на старите църковни основи от 1859 г. Преди това на 5 декември 1890 г. били извадени тленните останки на погребаните тук шестима архиереи – Авксентий Велешки, Паисий Пловдивски, Иларион Търновски (Макариополски), Доротей Скопски, Партений Нишавски и Аверкий Врачански. Те били почистени и поставени в специално направени отделни ковчежета. Намерени били и костите на Христо П. Тъпчилещов, но те щели да бъдат извадени от неговите близки и пренесени в София. На следващия ден, 6 декември, 1890 г. в „Дървената църква“ имало служба, на която архим. Григорий бил хиротонисан за Макариополски епископ. В края на службата бил отслужен молебен за здравето и дългоденствието на султан Абдул Хамид Втори. След това екзарх Йосиф и духовенството на храма отслужили заупокоен парастас за покойните митрополити, чиито тленни останки били извадени предния ден. Прочувствено слово за тях произнесъл самият екзарх.
Разчистването на старите основи започнало на 10 декември 1890 г. и приключило на 2 април 1891 г. За заздравяването на строителната площадка, която била стар насип, били доставени триста пилона от ливански кедър, дълги по двадесет метра и с диаметър шестдесет сантиметра. На 12 юни 1891 г. бил забит първият пилон. Отначално ги набивали ръчно, като десет-петнадесет души работници за около една седмица набивали по един. За да не се протака работата, доставили от Англия специална парна машина, с която свършили бързо и лесно. Върху така заздравения терен били изградени нови основи от гранит, облицовани с мрамор.
Основният камък на новата църква бил положен от екзарх Йосиф Първи на 26 април 1892 г. след отслужване на св. Литургия в старата „Дървена църква“. Присъствали Скопският митрополит Максим, архим. Софроний, управляващ Одринска епархия, протосингелът ик. Георги Хаджитилев, българският дипломатически агент в Цариград Петър Димитров и всички чиновници от агентството и Екзархията, български търговци, еснафи и др. Под олтара на вече изградените основи положили каменно ковчеже, в което сложили различни монети и металическа плочка със следния надпис: „Во славу Святия, единосущния, животворящия и неразделимия Троици, Отца и Сина и Святаго Духа: при державе августейшаго господаря султана Абдул Хамид Хан Втораго и при Блаженнейшем Йосифе Первом, екзархе Болгарском, положи се им же самим основний камен святому храму сему во имя Святаго апостола первомученика и архидякона Стефана, созидаемому помощию и иждивением болгарского народа в памет своего духовнаго возрождения. Лета от сотворения мира 7400, от рождества же по плоти Бога Слова 1892, индикта 5, месеця априлиа 26, в царствующем Цариграде в Фенер“.
Ик. Георги Хаджитилев прочел надписа пред множеството, поставили го в каменното ковчеже и той бил замазан с хоросан собственоръчно от екзарх Йосиф, след него от Скопския митрополит Максим, агента П. Димитров и някои други официални лица. След това строителната комисия дала скромна закуска в българското училище във „Фенер“, на която присъствали около стотина души. След закуската българският банкер в Цариград А. Стоянович поканил гостите да отидат на Кеатханата и там да продължат празненството на негова сметка. Мнозина отишли и веселбата траяла чак до вечерта.
По преценка на архитекта Ховсеп Азнавур само основите били направени от гранит, а останалата конструкция трябвало да бъде желязна и разглобяема – при евентуално поддаване на основите да бъде демонтирана и преместена на друго място. Чрез българския дипломатически агент в Цариград д-р Георги Вълкович изработката на желязната конструкция била възложена на фирмата на Рудолф Филип Вагнер (1827-1888), основана през 1854 г. във Виена, (същата фирма е изработила железните парапети на Лъвов и Орлов мост в София). Специалисти от фирмата под опитното ръководство на инж. Паул Нойман (малко по-късно професор в Бърно) изготвили новите технически проекти и хилядите елементи били отлети, изковани и валцовани за около две години. След това в двора на фабриката, във Виенския квартал „Майдлинг“, Желязната църква била пробно сглобена. Нейният величествен вид привлякъл вниманието на виенчани и в няколко тамошни вестника се появили статии с нейното описание. Разгледали я най-внимателно група членове на инженерно-архитектурното дружество, които дали отлична оценка за умелата изработка пред главния директор на фирмата Гюнтер. Дори ерцхерцог Карл Людвиг с двете си дъщери в продължение на цял час разглеждал българската църква на 2 октомври 1895 г. и се произнесъл „извънредно похвално за нея“. Българският архитект Янаки Шамарджиев бил упълномощен да отиде във Виена и да я приеме.
След приемането ѝ тя била демонтирана и отделните елементи били щателно пакетирани и изпратени с влак до Триест. Там били натоварени на параходи и пренесени в Цариград. Първата пратка от двадесет тона железни елементи пристигнала с два парахода на компанията „Лойд“ на 22 ноември 1895 г. От фирмата на фон Вагнер били командировани петнадесет работници-монтьори, които под опитното ръководство на главния майстор Хакер започнали сглобяването на църквата върху готовите каменни основи. Според предварително сключения договор окончателното ѝ завършване трябвало да стане през месец април 1896 г.
През март 1896 г. българският княз Фердинанд пристигнал на официално посещение в османската столица. На Връбница, 17 март 1896 г., той ходил с цялата си свита да се черкува в старата „Дървена църква“ и след това с интерес разгледал строящата се „Желязна църква“, на която оставало да се сложи покривната конструкция. Преди тръгването си от Цариград българският монарх подарил хиляда златни лева за новата българска църква.
Сглобяването на „Желязната църква“ приключило на 14 юли 1896 г. и според договора тя била прегледана от специална техническа комисия, която съставила протокол за здравината ѝ. Възникнал обаче малък проблем около формата на иконостаса, понеже той бил изработен по западен, римокатолически образец. Наложило се да изпратят в Москва главния секретар на Екзархията Атанас Шопов и арх. Азнавур, да преговарят по изработката на нов иконостас в източноправославен стил. Планът на иконостаса бил изработен от Ховсеп Азнавур, а прегледан и одобрен от проф. Николай Василиевич Покровски от Духовната академия в Санкт Петербург и от арх. Григорий Иванович Котов от С.-Петербургската академия на изкуствата. За направата му бил сключен договор с придворния фабрикант Николай Алексиевич Ахапкин. Иконостасът без иконите щял да струва двадесет хиляди рубли. Изписването на иконите било възложено на московския живописец акад. Клавдий Василиевич Лебедев (1852-1916), като те щели да бъдат копия от известни икони на знаменити руски иконописци.
В края на октомври 1897 г. бил подписан договор с фирмата „Д. Сотиров и сие“ от София за постилане пода на църквата с мрамор, доставян от България. В пълен ход било и благоустрояването на терена около самата църква, както и строителството на преградна стена с малко пристанище откъм морето.
Най-сетне новият железен храм бил окончателно завършен. Той бил разположен перпендикулярно на брега на залива Златния Рог, като олтарът бил към морето. Размерите му били: дължина 28 м и широчина 14 м. Формата му била продълговата с къси странични криле. Над преддверието се издигала елегантна двадесет и четири метрова камбанария. В нея били поставени шест камбани с различна големина, отлети в камбанолеярната на синовете на П. И. Оловианишников в Ярославъл, Русия. Най-голямата камбана има диаметър 94 см и тежи 444 кг. На нея има надпис, който гласи: „Благодатна новина носи радост на земята и възхвалява славата на Господа в небесата“. Цялата метална конструкция на църквата тежала петстотин тона и външно била боядисана в сивосинкав цвят.
Тържественото освещаване на новата църква „Св. Стефан“, наричана още „Желязната църква“, било извършено от екзарх Йосиф Първи на 8 септември 1898 г. (именния ден на българската княгиня Мария-Луиза). В тържествената служба взели участие митрополитите Григорий Доростоло-Червенски, Симеон Варненско-Преславски, Константин Врачански, Григорий Пелагонийски, Гервасий Сливенски, Методий Старозагорски, Авксентий Велешки, Иларион Неврокопски и бившият Скопски митрополит Максим, управляващ Ловчанска епархия, заедно с мнозина монаси и свещеници. Присъствали много гости от Княжество България, от Македония и от Одринска Тракия. Службата започнала рано сутринта в старата „Дървена църква“, която била покрита цялата в зеленина. Целият църковен двор и околните улици били запълнени от гости-богомолци. Към осем и половина часа от старата църква излязла лития, начело с хоругви, с ковчеже със св. мощи и другите църковни ценности. Литията обиколила новия храм и влязла вътре, където започнало самото му освещаване. По време на литургията екзархът произнесъл прочувствено слово.
След свършването на църковната служба висшите духовни лица и видните гости от Княжество България посетили българския дипломатически агент Димитър Марков и му поднесли приветствията си по случай именния ден на българската княгиня. След това в ресторант „Пера-Палас“ строителната комисия дала банкет на по-първите гости на освещаването на „Желязната църква“. На следващия ден, 9 септември 1898 г., тържествената архиерейска служба по освещаването на новия храм била повторена, тъй като специалният влак с гостите-богомолци от България бил закъснял и те изтървали самото освещаването. След службата екзарх Йосиф и останалите владици приемали и благославяли гостите в стаите на метоха.
След освещаването на новия храм, старата „Дървена църква“, която се намирала точно пред главния му вход, била разрушена, а четиридесет дни по-късно и теренът бил очистен. Запазен бил само напрестолният камък, който и до днес стои като скромен паметник, напомняйки за историческата роля, която скромната църквица играла в продължение на половин век. До запазения напрестолен камък били поставени мраморни надгробни плочи на тримата бележити йерарси, титаните на църковно-народната борба Авксентий Велешки, Паисий Пловдивски и Иларион Търновски (Макариополски). В близост до тях се намира и надгробният паметник на Въла Йовчева, сестрата на екзарх Йосиф Първи, която починала в Цариград през 1887 г. На 14 август 1924 г. починал екзархийският заместник Велешки митрополит Мелетий, който бил погребан вдясно до църковните стъпала на главния вход.
