Od 1869 proboszcz kolechowickiej parafii, ks. Antoni Dudziński, ubiegał się o środki państwowe na budowę nowej cerkwi, argumentując, iż starsza była już poważnie zniszczona (z uszkodzoną podłogą, dachem i ścianami). Wnętrze świątyni opisywał jako podobne do wnętrz katolickich kościołów. Prace budowlane nad nową, murowaną świątynią, rozpoczęto jednak dopiero w 1879. Pracami kierował mistrz Bazyli Kobuz z Homla, zaś projekt obiektu wykonał architekt gubernialny Tomasz Orłowski. Cerkiew poświęcił 9 lutego 1883 ks. Teodor Lachowski, dziekan dekanatu włodawskiego. W 1893 do świątyni uczęszczało 523 parafian. Cerkiew była przeznaczona do równoczesnego udziału 150 osób w nabożeństwieOswiaszczenije cerkwi w s. Kolechowicach Włodawskago ujezda, „Chołmsko-Warszawskij Jeparchialnyj Wiestnik”, nr 34, r. XXVI, s. 408.. W tym samym roku obiekt wizytował biskup lubelski Gedeon. W 1911 świątynia została poświęcona powtórnie po tym, gdy we wnętrzu wybuchł pożar od pozostawionej świecy wotywnej. Ceremonii przewodniczył ks. Ignacy Krynicki, dziekan włodawski. Cztery lata później miejscowa ludność prawosławna udała się na bieżeństwo, w czasie którego świątynia została porzucona. Część wyposażenia (utensylia liturgiczne, dzwony) została wywieziona, resztę rozgrabiła miejscowa ludność oraz wojska austriackie.