Budynek został wzniesiony w stylu klasycystycznym, ale to co możemy zobaczyć dzisiaj to efekt gruntownej przebudowy dokonanej przez Rosjan w końcu XIX wieku, po wcześniejszym przejęciu świątyni przez Cerkiew prawosławną (na mocy carskiego dekretu z 1875 roku o delegalizacji Unii Brzeskiej). Rosjanie w czasie tej przebudowy w końcu XIX wieku nadali budynkowi świątyni typowe cechy stylu bizantyjsko-rosyjskiego, który dziś dominuje nad elementami stylu klasycystycznego. Murowany budynek świątyni jest orientowany, zbudowany na planie krzyża greckiego. Położony jest na skraju skarpy ponad doliną Włodawki i Bugu, otoczony zielenią (dziś częściowo zaniedbaną, niegdyś był tu cmentarz). Cerkiew Narodzenia Najświętszej Maryi Panny zajmuje cichy zaułek przy południowym, niższym krańcu ulicy Kościelnej, nad której północnym, wysokim krańcu stoi kościół katolicki.

Dzisiaj świątynia jest odnowiona (została częściowo zdewastowania po drugiej wojnie światowej i wysiedleniu Ukraińców) i służy bardzo nielicznej już grupie włodawskich i okolicznych prawosławnych.

Świątynie odwiedzaj też setki wiernych i turystów, zwłaszcza w czasie włodawskiego Festiwalu Trzech Kultur, kiedy to w cerkwi mają okazję zapoznać się z prawosławnymi tradycjami miasta i regionu.

W latach 1890-91 obiekt przebudowano, dobudowując prawdopodobnie dwie nawy boczne. Po wysiedleniu Ukraińców w 1946 roku cerkiew została zamknięta na 10 lat. Nabożeństwa ponownie zaczęto odprawiać dopiero w 1956 roku.

Wnętrze świątyni pokryte jest klasycystyczną polichromią. Wewnątrz znajduje się bogaty ikonostas z XIX w. i liczne zabytkowe elementy wyposażenia z XVIII-XIX w.