Pierwsza cerkiew św. Mikołaja w Białymstoku, położona w pobliżu dzisiejszego soboru była filią świątyni w Dojlidach. Według niektórych źródeł istniała już w XVI stuleciu. Według innych małżeństwo Jana Klemensa i Katarzyny Barbary Branickich ufundowało unicką cerkiew św. Mikołaja przed 1727 – z tego roku pochodzi dokument (z 9 lutego 1727 roku – najdawniejszy dokument dla cerkwi św. Mikołaja w Białymstoku), w którym Branicki ofiarowywał 25 złotych dla jej proboszcza w intencji zmarłych ze swojej rodziny. Jest to najstarsza wzmianka o funkcjonowaniu świątyni tego obrządku. Prawdopodobnie jednak fundacja cerkwi unickiej nastąpiła jeszcze w końcu XVII w., w latach 1694–1696, w okresie dynamicznego rozwoju miasta. Fundując ją, Stefan Mikołaj Branicki zbudował cerkiew dla nowo napływających do miasta mieszkańców. Za taką hipotezą, przedstawioną przez Przemysława Czyżewskiego, świadczy napis na cerkiewnym antyminsie, który został podpisany przez biskupa Leona Załęskiego w 1708. Budowa nowej świątyni miała związek ze wzrostem liczby mieszkańców Białegostoku wskutek rozwoju miejscowego przemysłu oraz ze wzrostem liczby prawosławnych, wynikającym z likwidacji Kościoła unickiego w Imperium Rosyjskim (poza diecezją chełmską) oraz z napływu urzędników rosyjskich. W październiku 1838 wykonanie projektu cerkwi powierzono architektowi eparchialnemu Michajłowowi, brak jednak jednoznacznych dowodów, że to on jest autorem planu budynku. W 1840 zatwierdzony został projekt nowej świątyni. 21 marca 1843 kamień węgielny nowej cerkwi poświęcił przełożony monasteru w Supraślu, archimandryta Nikodem. W latach 1843–1846 obok drewnianej cerkwi wzniesioną nową, zaś po zakończeniu prac starszy budynek rozebrano. Zlikwidowano również cmentarz, który pierwotnie otaczał cerkiew św. Mikołaja, a zachowane nagrobki przeniesiono na wzgórze z kaplicą św. Marii Magdaleny. Łączny koszt budowy wyniósł ponad 36 tys. rubli srebrem, z czego niecałe 3 tys. przekazał skarb państwa. Nowa świątynia od początku swojego istnienia była siedzibą prawosławnej parafii, przejmując funkcje urządzonej w 1830 kaplicy św. Aleksandra Newskiego w pałacu Branickich.

Nową świątynię wzniesiono w stylu klasycystycznym, z elementami nawiązującymi do architektury antyku, jak i do bizantyńskich świątyń krzyżowo-kopułowych. Pracami budowlanymi kierował Dawid Zabłudowski. W 1846 świątynia została oddana do użytku i poświęcona przez metropolitę wileńskiego i litewskiego Józefa, który wcześniej szczególnie wspierał starania na rzecz jej budowy. Została drugą katedrą eparchii wileńskiej i litewskiej, w randze soboru. Do 1850 uzyskała komplet niezbędnego wyposażenia. Według spisu wyposażenia z 1859 na jej dzwonnicy znajdowało się pięć dzwonów, zaś Białostocka Ikona Matki Bożej była obiektem kultu zarówno ludności prawosławnej, jak i katolickiej. Pierwszy remont obiektu miał miejsce w latach 1868–1872. Dwanaście lat później wierni ufundowali wstawienie do świątyni ikony św. Aleksandra Newskiego, co miało upamiętnić koronację cesarza Aleksandra III i jego małżonki Marii Fiodorowny.

25 sierpnia 1897 cerkiew odwiedzili cesarz Mikołaj II i jego małżonka Aleksandra Fiodorowna. Na pamiątkę ich wizyty sobór otrzymał od prywatnych ofiarodawców dary na zakup Ewangeliarza w srebrnej oprawie. Wnętrze soboru od początku jego funkcjonowania zdobiły freski, jednak pierwsza kompozycja, wykonana w latach budowy, uległa zniszczeniu jeszcze przed 1910. W wymienionym roku grupa malarzy rosyjskich pod kierownictwem Michaiła Awiłowa wykonała nową dekorację, wzorując się w swojej pracy na freskach Wiktora Wasniecowa z soboru św. Włodzimierza w Kijowie. W 1910 przeprowadzono także remont cerkiewnego dachu.

W 1900, w związku ze zmianą granic administracyjnych eparchii, cerkiew w Białymstoku znalazła się w eparchii grodzieńskiej. Ponownie została drugą katedrą eparchii. 24 października 1910, po zakończonym remoncie, obiekt został ponownie konsekrowany przez biskupa grodzieńskiego i brzeskiego Michała.

Budynek znajdował się przy ówczesnej ulicy Choroskiej, przy Bramie Choroskiej, był drewniany, malowany na żółto i szaro, z czerwonymi kopułami. Z 1748 pochodzi pierwsza informacja o wikarym parafii w Dojlidach, którego obowiązkiem była obsługa cerkwi św. Mikołaja.