Została poświęcona 22 października 1877 roku. Cerkiew w stylu typowym dla dziewiętnastowiecznej architektury rosyjsko-bizantyjskiej, budowała sprowadzona do tego celu grupa majstrów z centralnej Rosji. Została wzniesiona z cegieł wypalanych w uroczysku Hłuboczok, gdzie urządzono prowizoryczną cegielnię. Kamienie niezbędne do utwardzenia fundamentów i budowy ogrodzenia zebrano na okolicznych polach, głównie w okolicach wsi Dobrowoda.
Cerkiew została poważnie uszkodzona podczas II wojny światowej w wyniku działań wojennych spowodowanych niemieckim kontruderzeniem po zajęciu Kleszczel przez Armię Czerwoną (25 lipca 1944). Dach i wyposażenie wnętrza uległy niemal całkowitemu spaleniu. Cerkiew została odbudowana w 1949 r., a ikony oraz ikonostas zostały przeniesione z wysiedlonej w wyniku akcji „Wisła” wsi w woj. lubelskim.
Na szczególną uwagę zasługuje ikona św. Mikołaja Cudotwórcy, która ocalała podczas działań wojennych, namalowana przez nieznanego mistrza w XVI w. Jest to niewątpliwie jedna z najstarszych ikon znajdująca się na całym Podlasiu. Cerkiew jest najwyższą budowlą w miasteczku. W każdą niedzielę można uczestniczyć w św. Liturgii odprawianej w języku starocerkiewnosłowiańskim.
