Obecna, murowana cerkiew p.w. MB Kazańskiej (dawniej Eliasza Proroka) została wybudowana w 1771 roku.
W 1874 roku po likwidacji unii, cerkiew Eliasza Proroka zostaje przekształcona na prawosławną. W 1880 roku malarze z Hrubieszowa - Zin i Olechwier malują cerkiew. Z setek prac Olechwiera zachował się do dziś tylko obraz Przemienienia Pańskiego na suficie wojsławickiej świątyni.
Obok cerkwi znajduje się murowana, wyniosła dzwonnica o baniastej, bizantyjskiej kopule.

W lipcu 2010 roku odbyło się w Wojsławicach, pierwsze w tej miejscowości, "Spotkanie Trzech Kultur". Z tej okazji, w cerkwi św. Eliasza Proroka, po raz pierwszy po 65 latach, odprawiono nabożeństwo (Wieczernia).

W Wojsławicach były jeszcze dwie inne cerkwie pw. św. Praksedy i św. Onufrego.
Zbudowaną w 1725 roku przy ul. Krasnystawskiej cerkiew św. Praksedy (kolejnej po cerkwi (?)św. Paraksewii-Piatnicy wg. Andrzej Gil - "Prawosławna Eparchia Chełmska do 1596r"), odnotowano już w 1793 roku jako "zupełnie zdezelowaną".
Natomiast cerkiew pw. św. Onufrego (przy ul. Grabowieckiej) została zniszczona w pożarze w 1779r.