Cerkiew wzniesiono w 1878 r. w miejscu wiekowej, drewnianej świątyni prawosławnej.
14 października 2007 r. w dniu patronalnego święta obchodzono jubileusz 500-lecia powstania parafii prawosławnej i nadania praw miejskich Choroszczy. Arcybiskup białostocki i gdański Jakub po uroczystej Świętej Liturgii poświęcił pamiątkową tablicę umieszczoną na głazie przed cerkwią. Arcybiskup Jakub w uznaniu zasług ks. Andrzeja Bołbota, proboszcza parafii Opieki Matki Bożej w Choroszczy, wręczył mu order świętej równej Apostołom Marii Magdaleny II stopnia. Burmistrz Choroszczy – Jerzy Ułanowicz, przekazał natomiast duchownemu pamiątkowy dyplom ze słowami uznania za zasługi dla parafii i miasta[1].
Pod względem architektonicznym cerkiew utrzymana jest w stylu rosyjskiego neobizantynizmu. Nad skrzyżowaniem transeptu z nawą wznosi się niewielka sygnaturka, która 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ę – u dołu czworoboczną, na górze ośmiokątną z hełmem i cebulastą kopułką zwieńczoną prawosławnym krzyżem. Nasady dolnej i górnej kondygnacji zdobią kokoszniki, które wykorzystano także w zewnętrznych bocznych ścianach nawy głównej świątyni, gdzie przejęły rolę nadokienników. Obiekt dekorują także liczne gzymsy i pilastry symptomatyczne dla architektury neoklasycyzmu. Cerkiew parafialna w Choroszczy jest świątynią orientowaną, co oznacza, że jej podłużna apsyda, owalnie zamykająca prezbiterium, jest skierowana w kierunku wschodnim. Obiekt wzniesiony został na planie krzyża greckiego.
