Początkowo parafia sokólska korzystała z przenośnej cerkwi wojskowej stacjonującego w mieście pułku Kutuzowsko-Smoleńskiego, następnie z wynajmowanych pomieszczeń, zaś od 1848 z cmentarnej cerkwi św. Aleksandry. W 1850 opracowany został plan budowy obszerniejszego obiektu sakralnego. Świątynia powstała w ciągu kolejnych trzech lat, za sumę 14 870 rubli, przy czym część prac za darmo wykonali parafianie. Gotowy obiekt poświęcił 26 kwietnia (9 maja) 1853 biskup brzeski Ignacy. W czasie budowy konieczna okazała się rezygnacja z niektórych założeń projektu budowlanego. Nie powiodło się urządzanie zakrystii w podziemiach budynku z powodu nadspodziewanie wysokiego poziomu wód gruntowych. Również wykorzystanie bocznych kopuł cerkwi jako dzwonnic okazało się niemożliwe i zmusiło budowniczych do wzniesienia dzwonnicy jako odrębnej konstrukcji, pełniącej równocześnie funkcje bramy prowadzącej na teren świątyni. Obiekt ten został oddany do użytku w 1869.