Pod koniec XV wieku Choroszcz z włością została nadana bojarowi z Kijowszczyzny – Iwanowi Chodkiewiczowi, którego spadkobierca – Aleksander, przekazał Choroszcz prawosławnemu monasterowi z Supraśla. Najpewniej w 1507 roku mnisi wznieśli w Choroszczy cerkiew, a opieką duszpasterską otaczali prawosławnych mieszkańców Choroszczy i okolic aż do 1609 roku, gdy klasztor zmuszony był przyjąć unię. W tym czasie Choroszcz stała się samodzielną parafią unicką.

Parafia prawosławna w Choroszczy powstała w 1507 roku. Stanęła wówczas drewniana cerkiew pod wezwaniem Opieki Matki Bożej. Na początku XVII wieku wierni obrządku wschodniego przyjęli unię brzeską. W 1641 roku w Choroszczy pobudowano nową drewnianą cerkiew. Jej fundatorką była Anna Pac. Świątynię wyremontował Jan Klemens Branicki. Dach cerkwi został pokryty dachówką, ściany otynkowano wapnem, fundamenty wzmocniono cegłami. W II połowie XVIII wieku świątynia ponownie podupadła. Odnowiona w latach 30-tych XIX wieku, jednak jej stan nadal pozostawał wiele do życzenia. W dodatku wokół cerkwi była zabudowa żydowska. W 1865 roku choroska Cerkiew otrzymała od władz rosyjskich skonfiskowane budynki zakonu dominikanów, gdzie zamieszkał proboszcz oraz psalmista. Inicjatorem budowy nowej, murowanej cerkwi był ksiądz Teodor Jaszyn. W 1880 roku pożar strawił 50 domów. Rosjanie przystąpili do planowej odbudowy miasteczka. Wytyczono też drogę, która miała prowadzić do miejsca lokalizacji nowo planowanej cerkwi. Jej budowę zatwierdzono 29 kwietnia 1880 roku. Fundamenty stanęły w październiku 1881 roku. Poświęcono ją 1 października 1883 roku.

W 1807 roku, za sprawą zapisów traktatu z Tylży, Choroszcz znalazła się w zaborze rosyjskim. Brak archiwaliów (w roku 1915, w obawie przed zbliżającym się frontem, władze carskie wywiozły do Rosji m.in. cerkiewny dzwon i archiwum) sprawił, że losy parafii w XIX wieku nie zostały zbadane. W 1839 roku wierni obrządku wschodniego wrócili na łono swego kościoła. Do 1900 roku miejscowa parafia należała do Diecezji Litewsko-Wileńskiej.

Powstanie w Choroszczy największej w regionie fabryki sukna i kortów oraz dynamiczny rozwój regionu przyczynił się do zwiększenia liczby mieszkańców, głównie ewangelików i Żydów. Dzięki ofiarności parafian i licznych darczyńców, w latach 60. XIX wieku, miejsce starej drewnianej cerkwi, zajęła nowa murowana świątynia. Cerkiew została zbudowana w latach 1881-1883. Budowniczym był, przybyły z Rosji – ojciec Teodor Jaszyn. Świątynię wyświęcono 1 października 1883 roku.

Cerkiew zbudowano stylu neobizantyjskim, na planie greckiego krzyża – z nieznacznym przesunięciem w kierunku zachodnim; ołtarz poprzedniej cerkwi upamiętnia do dziś metalowy krzyż. Cerkiew parafialna w Choroszczy jest świątynią orientowaną, co oznacza, że jej podłużna apsyda (pomieszczenie na rzucie półkola, „dostawione” do bryły świątyni), owalnie zamykająca prezbiterium, jest skierowana w kierunku wschodnim.

Obiektu jest murowany, z cegły, tynkowany. W nawie głównej znajduje się murowana pozorna kopuła. Prezbiterium i łącznik ze sklepieniem kolebkowym. Korpus cerkwi założony na planie kwadratu (krzyża greckiego) z wysuniętym prezbiterium, zakończonym półkoliście od wschodu oraz wieżą na planie kwadratu – od strony zachodniej. Bryła świątyni rozczłonkowana, z wysoką wieżą nakrytą hełmem. Niższy korpus obiektu jest kryty dachem czterospadowym z dwiema sygnaturkami i hełmami cebulastymi, prezbiterium wieńczy spłaszczona kopuła; łącznik kryty dachem dwuspadowym.

Kopuła, wraz z czterema sąsiednimi wieżyczkami i krzyżami na ich szczycie, symbolizuje Jezusa Chrystusa i czterech Ewangelistów. Do cerkwi wchodzi się przez trzykondygnacyjną dzwonnicę o niesymetrycznym kształcie: u dołu jest czworoboczną, a na górze ośmiokątną, z hełmem i cebulastą kopułą zwieńczoną prawosławnym krzyżem. Nasady dolnej i górnej kondygnacji zdobią kokoszniki (ozdobne elementy wystroju, w kształcie łuku koszowego), które wykorzystano także w ścianach nawy głównej świątyni, gdzie przejęły rolę nadokienników. Obiekt dekorują także gzymsy i pilastry charakterystyczne dla architektury neoklasycyzmu.

W roku 1928 zakupiono w Bacieczkach dom, który po przetransportowaniu do Choroszczy, stał się siedzibą plebanii. Dzięki staraniom ks. Włodzimierza Gorustowicza – od 1929 roku proboszcza parafii, w 1937 roku przywieziono z monastyru w Poczajowie na Ukrainie kopię tamtejszej cudownej Ikony Matki Bożej. Znajduje się ona w choroszczańskej cerkwi do dziś – Poczajowska Ikona Matki Bożej jest umiejscowiona nad królewskimi wrotami ikonostasu.

We wnętrzu, w carskich (królewskich) wrotach ikonostasu cztery tonda ukazują Ewangelistów: Mateusza, Marka, Łukasza i Jana, piąte zaś przedstawia Zwiastowanie Przenajświętszej Bogurodzicy. Z lewej strony, za diakońskimi wrotami znalazła miejsce ikona Św. księcia Aleksandra Newskiego.

W 1883 roku nowa świątynia była już pokryta dachem z blachy. W tym samym roku zamontowano ikonostas. Do parafii należeli wierni z Choroszczy, Ruszczan, Żółtek, Rogowa, Barszczewa, Jeronik, Sienkiewicz, Oliszek, Dzikich, Śliwna i Rogowa-Majątku. W 1899 roku plac cerkiewny otoczono kamiennym parkanem.

Zmiany w układzie granic państwa spowodowały utworzenie nowych diecezji, a tutejsza parafia uzyskała od władz państwowych status etatowej i weszła w obręb diecezji grodzieńsko nowogrodzkiej Metropolii Warszawskiej.

W 2007 roku w świątyni choroszczańskiej obchodzono jubileusz 500-lecia powstania parafii prawosławnej. Arcybiskup Białostocki i Gdański Jakub poświęcił pamiątkową tablicę umieszczoną na głazie znajdującym się przed cerkwią.