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.