Pierwsze wzmianki o cerkwi prawosławnej p.w. św. Paraskiewy - Piatnicy w Krasnymstawie sięgają 1505 roku. Właśnie Piatnicki duchowny wspomina się w lustracji 1564-1565 r. (patrz. Andrzej Gil - Prawosławna Eparchia Chełmska do 1596 r. - Lublin, Chełm 1999 r. str. 229.) W dokumencie 1632 r. wspomina się, że proboszcz tejże świątyni przeszedł z Kościoła Prawosławnego na uniatyzm. Zatem przez 36 lat prawosławni stawili opór Kościołowi Unickiemu przemocą narzuconemu przez ówczesną politykę. Wyżej wspomniana świątynia została rozebrana przez Austriaków w XVIII stuleciu.

W 1870 roku nieczynny kościół rzymskokatolicki przekazany został na cerkiew grekokatolicką. Z momentem kasacji unii w 1875 r. ta świątynia Narodzenia NMP została przejęta przez Kościół Prawosławny. Akta historyczne dotyczące tych wydarzeń znajdują się w Centralnym Państwowym Historycznym Archiwum Ukrainy we Lwowie. Po ewakuacji społeczności prawosławnej w głąb Rosji w 1914 - 1915 r. (tzw. bieżeństwo) tematyczną świątynię przejął Kościół Katolicki. Podczas okupacji niemieckiej, przez kilka lat, znowu świątynia należała do prawosławnych, przy której funkcjonowała siedziba Prawosławnego Dekanatu Krasnostawskiego. Po wyzwoleniu na skutek masowego wysiedlenia społeczności prawosławnej z Krasnegostawu i okolicy w głąb radzieckiej Ukrainy zakończyło się funkcjonowanie i obecność Kościoła Prawosławnego w Krasnymstawie. Na miejscowym cmentarzu pozostało jeszcze do dnia dzisiejszego kilkanaście pomników świadczących o bogactwie tradycji wschodniej w Krasnymstawie.