Myśl wzniesienia w Białymstoku cerkwi Hagia Sophia zrodziła się w 1986 roku w samolocie. Wracali wtedy z Konstantynopola, po złożeniu wizyty u patriarchy konstantynopolitańskiego Dymitriosa I, ówczesny zwierzchnik Cerkwi Prawosławnej w Polsce metropolita Bazyli, arcybiskup diecezji białostocko-gdańskiej Sawa, od 1998 roku metropolita oraz o. Aleksander Chilimoniuk, proboszcz parafii Wszystkich Świętych w Białymstoku.
Goście patriarchy odwiedzili słynną konstantynopolitańską Hagia Sophię. Nie mogli się w niej modlić. Zabraniało im tego tureckie prawo. Wiedzieli też, że nie można zanosić modlitw w trzech innych sławnych świątyniach Hagia Sophia w Kijowie, Połocku, Nowogrodzie Wielkim. Wszystkie znajdowały się na terenie Związku Radzieckiego, walczącego przez siedemdziesiąt lat z Cerkwią. „Jeśli powstanie w Białymstoku kolejna świątynia, niech nosi wezwanie Hagia Sophia. Niech chociaż w tej świątyni Mądrości Bożej będzie zanoszona modlitwa” – pomyślano wtedy.
Cerkwie Hagia Sophia, po słowiańsku Premudrosti Bożijej, po polsku Bożej Mądrości, należały do najokazalszych, najpiękniejszych i najbardziej znaczących. Fundowali je cesarze i książęta w Konstantynopolu, Sofii, Ochrydzie, Kijowie, Połocku, Nowogrodzie Wielkim, Salonikach. W późniejszym okresie powstały również w Waszyngtonie, Los Angeles, Londynie, Bazylei (Szwajcaria), Harbinie (Chiny).
Kamień węgielny pod budowę cerkwi Hagia Sophia w Białymstoku położono 20 listopada 1987 roku. Pięć lat wcześniej, 18 czerwca 1982 roku, ówczesny arcybiskup diecezji białostocko-gdańskiej Sawa utworzył nową parafię Wszystkich Świętych przy cmentarnej cerkwi pod tym samym wezwaniem w Białymstoku przy ulicy Wysockiego 1. Ta parafia stanie się matką nowej prawosławnej wspólnoty Świętej Sofii – Mądrości Bożej – Hagia Sophia. Proboszczem parafii Wszystkich Świętych został mianowany o. Aleksander Chilimoniuk, dotychczasowy wikariusz białostockiej katedralnej parafii św. Mikołaja, na którego barkach spocznie trud pierwszego, bardzo trudnego etapu wznoszenia cerkwi Hagia Sophia i organizowania przy niej parafialnej wspólnoty. Nowa parafia przy Wysockiego gromadziła wiernych z rozległej dzielnicy Wygoda. Parafialna, cmentarna cerkiew była malutka. Mieściła około sto osób. Potrzeba budowy nowej świątyni była koniecznością.
Władze województwa białostockiego wydały 23 grudnia 1986 roku decyzję o lokalizacji nowej parafii przy ulicy Trawiastej w Białymstoku. W roku następnym przygotowania do budowy nabierały tempa. 20 marca podpisano notarialny akt kupna działki o powierzchni 8169 metrów kwadratowych pod budowę świątyni i domu parafialnego.
20 listopada 1987 roku miało miejsce historyczne wydarzenie. Na plac budowy przybył patriarcha Konstantynopola Dymitrios I. W obecności ówczesnego arcybiskupa diecezji białostocko-gdańskiej Sawy i proboszcza parafii Wszystkich Świętych o. Aleksandra Chilimoniuka dostojny gość poświęcił kamień węgielny pod budowę cerkwi Hagia Sophia.
Po czterystu latach białostocką ziemię znów odwiedził patriarcha Konstantynopola. Poprzednią wizytę tak dostojnego gościa odnotowano w 1589 roku. Patriarcha Jeremiasz II gościł wtedy w supraskiej ławrze.
W niespełna rok po wmurowaniu aktu erekcyjnego, 6 września 1988 roku, arcybiskup Sawa erygował samodzielną wspólnotę świętej Sofii – Mądrości Bożej – Hagia Sophia. Teren nowej parafii wydzielił z parafii Wszystkich Świętych. Hierarcha w swym dekrecie zaznaczył, że wspólnota będzie na razie korzystała z cerkwi Wszystkich Świętych i tymczasowej kaplicy, powstałej na placu budowy oraz cmentarza przy ulicy Wysockiego.
Niemal równolegle z budową cerkwi, trwało wznoszenie domu parafialnego. 21 września 1990 roku podczas parafialnego święta Narodzenia Bogarodzicy, arcybiskup Sawa poświęcił kamień węgielny i wmurował akt erekcyjny pod nowy dom, projekt którego wykonał architekt Michał Bałasz.
Cerkiew pięła się w górę. Jej elewację wykonano z cegły klinkierowej. Jedynie przy wejściu głównym zastosowano połacie tynku, malowanego na biało. Na bocznych ścianach – południowej i północnej – kładziono misterne wzory z płycin i pilastrów, przechodzących w przenikające się łuki. Ich gra, zwłaszcza przy bocznym oświetleniu, wskazuje na wysoki kunszt budowlanego rzemiosła.
Wznoszenie cerkwi obserwowali wierni nowej parafii. O. Aleksander Chilimoniuk stworzył im ku temu możliwość. Jak tylko zbudowano na placu długi, drewniany barak, służący jako magazyny i warsztaty, proboszcz kazał jego część przeznaczyć na tymczasową świątynię. W baraku modlono się w latach 1987-1996. To integrowało społeczność, wiązało ją z nowym miejscem i czyniło odpowiedzialną za ogromny trud budowy tej niepowtarzalnej cerkwi. W 1991 roku, podczas święta Narodzenia Bogarodzicy, arcybiskup Sawa poświęcił pierwszy krzyż, który następnie ustawiono na głównej kopule cerkwi. Krzyż, wraz z kulą u jej podstaw, ma około czterech metrów wysokości.
31 maja 1992 roku postawiono krzyże na czterech mniejszych kopułach. W 1992 roku świątynia przybrała z zewnątrz wygląd taki, jaki znamy. Przykryto wtedy miedzianą blachą pięć kopuł świątyni.
Liturgię Świętą podczas święta parafialnego obchodzonego 21 września po raz pierwszy odsłużono wewnątrz budującej się cerkwi w 1994 roku. Na uroczystość przybył arcybiskup diecezji białostocko-gdańskiej Sawa, który poświęcił siedem dzwonów, wykonanych w Woroneżu w Rosji.
1 sierpnia 1995 roku, arcybiskup Sawa powołał o. Anatola Konacha na proboszcza parafii Hagia Sophia. Wikariuszem został wyznaczony o. Anatol Hajduczenia, natomiast diakonem o. Dymitr Tichoniuk.
15 pażdziernika 1998 roku do cerkwi Hagia Sophia przybył patriarcha konstantynopolitański Bartłomiej I. Była to jego pierwsza wizyta w Polsce jako patriarchy. Przybył on na zaproszenie zwierzchnika Cerkwi Prawosławnej w Polsce oraz władz państwowych. Patriarsze towarzyszyli – metropolita warszawski i całej Polski Sawa, arcybiskupi: łódzki i poznański Szymon, przemyski i nowosądecki Adam, wrocławski i szczeciński Jeremiasz, lubelski i chełmski Abel, biskupi: hajnowski Miron, supraski Jakub oraz bielski Grzegorz. Dostojnemu gościowi towarzyszyli metropolici Cerkwi greckiej. Uroczystość wyświęcenia świątyni Hagia Sophia metropolita Sawa określił jako najważniejsze godziny wizyty patriarchy w Polsce. Zwrócił się on do dostojnego gościa – „To z waszej ojczyzny, od Świętych Ojców mamy fundament naszej wiary”.
Podczas uroczystości w cerkwi Hagia Sophia patriarcha udzielił sakramentu kapłaństwa młodemu mnichowi Jerzemu (Pańkowskiemu), od 2007 roku biskupowi, a od 2010 roku Prawosławnemu Ordynariuszowi Wojska Polskiego. Metropolita podziękował wiernym za wielką pomoc przy budowie cerkwi, za dzieło tysięcy ofiar, szczególnie zaś o. Aleksandrowi Chilimoniukowi, który jedenaście lat wcześniej to dzieło rozpoczął, o. Anatolowi Konachowi, który dzieło kontynuuje, architektowi cerkwi Michałowi Bałaszowi i prof. Konstantinosowi Ksenopoulosowi, Grekowi z Katerini, tworzącemu polichromię. Parafia Hagia Sophia objęła białostockie północno-wschodnie osiedla – Bagnówkę, Jaroszówkę, Pieczurki, Wyżyny oraz część Wygody.
Od 1992 roku cerkiew Hagia Sophia stała się miejscem, skąd 9 sierpnia wyruszają piesze pielgrzymki do monasteru Zwiastowania Bogarodzicy w Supraślu na święto Supraskiej Ikony Matki Bożej. Jest tu odprawiany molebien. Pierwsze grupy pielgrzymów były nieliczne. Z każdym rokiem strumień pątników pęczniał, dochodząc do dwóch tysięcy. Organizatorem pielgrzymki jest Bractwo Młodzieży Prawosławnej.
Parafia stała się również ośrodkiem upowszechniania cerkiewnej muzyki. Z inicjatywy arcybiskupa Sawy zorganizowano w 1997 roku pierwsze Białostockie Dni Muzyki Cerkiewnej. Jeden z koncertów, 24 września tego samego roku odbył się w cerkwi przy Trawiastej. Od tego czasu zawsze podczas Białostockich Dni koncertują tu chóry.
Największym wydarzeniem muzycznym stało się organizowanie od 2008 roku w Hagia Sophii koncertów chórów, będących laureatami międzynarodowego festiwalu Hajnowskie Dni Muzyki Cerkiewnej. Koncerty zawsze gromadzą wielu dostojnych gości i słuchaczy nie tylko z Białegostoku i nie tylko prawosławnych. Odbywają się w maju, tuż po zakończeniu przesłuchań i koncercie finałowym w Hajnówce.