Czas powstania parafii jest trudny do określenia. Zachowały się jednak dokumenty, mówiące o nadaniu dóbr ziemskich w XVI w. przez królową Bonę miejscowym parafiom: rzymskokatolickiej i prawosławnej. W następnych wiekach funkcjonowała w Sokółce parafia unicka, która z czasem zintegrowała się z parafią rzymskokatolicką.
Od podstaw parafia odrodziła się w 1837, na dwa lata przed oficjalnym powrotem unitów do prawosławia (synod połocki). Parafia nie była zbyt liczna (ok. 180 osób) i dopiero włączenie w latach 50. Wierzchlesia i Nowowoli, wsi odległych od Sokółki o 15 km wydatnie zwiększyło liczebność tej społeczności. Pierwsza cerkiew funkcjonowała przy jednostce wojskowej stacjonującej w Sokółce (pułk kutuzowsko-smoleński). W 1839 poświęcono prowizoryczną kaplicę pod wezwaniem św. Mikołaja.
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ą.
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.
Kalendarz Prawosławny 2013, Wydanie Warszawskiej Metropolii Prawosławnej, ISSN1425-2171, s. 226
Hierarchia i kler kościoła prawosławnego w granicach II Rzeczypospolitej i Polski powojennej w XIX–XXI wieku, ks. Grzegorz Sosna i m. Antonina Troc-Sosna, Ryboły 2012
