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.
