Nową cerkiew pod wezwaniem św. Aleksandra Newskiego wybudowano w latach 1850–1853. Konsekracji świątyni dokonał 26 kwietnia 1853 biskup brzeski Ignacy. W 1869 dobudowano dzwonnicę bramną.
13 sierpnia 1901 na miejscowym cmentarzu prawosławnym konsekrowano kaplicę cmentarną pod wezwaniem św. Pawły.
W 1908 z sokólskiej parafii wydzielono i erygowano samodzielną parafię pod wezwaniem Wszystkich Świętych w Nowowoli. Pomimo podziału parafia liczyła w owym czasie ok. 1600 osób. Połowa z nich była mieszkańcami Wierzchlesia.
W latach 1915–1919 parafia nie funkcjonowała ze względu na bieżeństwo. Wielu ewakuowanych parafian nie powróciło już do miasta i trzonem parafii zostało Wierzchlesie z przyległymi wsiami.
W latach 70. XX w. zbudowano kaplicę pod wezwaniem Wszystkich Świętych na cmentarzu w Nowowoli. W 1992 z parafii sokólskiej wydzielono samodzielną parafię pod wezwaniem św. Jerzego w Wierzchlesiu. W latach 2010–2013 odbudowano zburzoną w czasie II wojny światowej dzwonnicę.
Liczba wiernych i zasięg terytorialny W 2017 parafia liczyła 1015 osób zamieszkujących miejscowości: Sokółka, Chwaszczewo, Drahle, Jacowlany, Kol. Jałówka, Kraśniany, Makowlany, Miejskie Nowiny, Nowowola, Sierbowce i Sokolany.