Cerkiew unicką ufundował tu w 1605 Lew Sapieha, kanclerz Wielkiego Księstwa Litewskiego.
W 1738 została ona rozebrana. Nową – tę, która przetrwała do dziś – wystawiła rok później Anna z Sanguszków Radziwiłłowa (Witoroż należał wtedy do bialskiego hrabstwa Radziwiłłów). Świątynia ta służyła unitom do 1874, kiedy to w ramach represji zamieniono ją na cerkiew prawosławną. Po I wojnie została przejęta przez Kościół rzymskokatolicki, parafię erygowano w 1919 roku. W latach międzywojennych kościół był remontowany.
Trudne czasy przyszły wraz z II wojną światową. Ukraińcy zajęli szkołę w Witorożu, potem zażądali przekazania kościoła na cerkiew prawosławną. Parafianie go bronili, ale Ukraińcy zwrócili się o pomoc do Niemców. Oskarżyli katolickiego proboszcza o antyniemiecką działalność, ten został aresztowany i wywieziony do obozu koncentracyjnego. Niemcy zamknęli kościół, a następnie przekazali (maj 1940) prawosławnym. Ci ograbili świątynię i ją zdewastowali. Część wyposażenia zdołali ukryć parafianie, przechowywali je przez całą okupację. Duchowny prawosławny opuścił placówkę dopiero w 1943 roku. Kościół zwrócono katolikom w 1944, kiedy do Witoroża przybyły oddziały AK. Po wojnie przeszedł kilka remontów, m. in.: 1946 – pokrycie dachu blachą, 1960 – nowa podmurówka i podwaliny, 1965 – nowa wieżyczka na sygnaturkę, 1982 – remont wnętrza. Po ostatnim, zaczętym w 2007 wygląd kościoła dość znacznie się zmienił.
Kościół w Witorożu jest orientowany, zbudowany z drewna modrzewiowego, o konstrukcji zrębowej (zrąb z bali sosnowych), wzmocnionej lisicami, oszalowany. Z więźbą dachową dwustolcową o zdwojonej jętce. W rzucie ma kształt prostokąta. Nawa zbliżona jest do kwadratu, przylega do niej węższe, prostokątne, prosto zamknięte prezbiterium. Jest ono ujęte po bokach prostokątnymi zakrystią i skarbczykiem (wszystko razem ma szerokość nawy). Od frontu nawa poprzedzona jest niewielką kruchtą na rzucie zbliżonym do kwadratu. Drewniany chór muzyczny nadwieszony nad nawą ma pełny parapet o prostej linii. Wnętrze kościoła pokryte jest płaskim stropem, w aneksach belkowanym. Na prostej belce tęczowej wisi XVIII-wieczny, barokowy krucyfiks. Podłoga z desek. Okna kwadratowe, w deskowych obramieniach. Elewacja frontowa jest gładka, w trójkątnej części szczytowej ozdobnie oszalowana, w niej krzyż. Analogicznym szczytem zwieńczona jest kruchta. Nawa i prezbiterium przykryte są wspólnym (jednokalenicowym) dachem dwuspadowym, nad kruchtą jest daszek dwuspadowy, nad aneksami (zakrystia i skarbczyk) – pulpitowy. Wszystkie dachy blaszane.
Po ostatnim remoncie (oprócz tego, że ujawnił on piękno naturalnych, modrzewiowych desek skrytych wcześniej pod ciemnobrązową farbą) kruchta zyskała podcień. Jej dach przedłużono w szeroki okap, jest on ozdobiony lambrekinem wycinanym z deski i wsparty na ośmiu słupach z mieczami. Do tego doszła nowa wieżyczka na sygnaturkę nad stykiem nawy i prezbiterium. Wcześniejsza, sześcioboczna z wysoką iglicą, została zamieniona na neobarokową, z arkadowymi prześwitami.
Ołtarz główny jest neobarokowy, dwukondygnacyjny, z kompozytowymi kolumnami i akantowymi uszami. Na gzymsie dolnej kondygnacji rzeźby aniołów. W ołtarzu obrazy: w polu głównym Matka Boska z Dzieciątkiem (barokowy, XVII wiek) w metalowej sukience; w zwieńczeniu Chrystus Ukrzyżowany z początku XX wieku. Dwa ołtarze boczne również są neobarokowe (lata 20/30-te XX wieku), w stylistyce analogicznej do ołtarza głównego. W nich obrazy w tradycji barokowej, z 1 połowy XIX wieku: w lewym Matka Boska z Dzieciątkiem, w prawym Archanioł Michał. Na wyposażeniu kościoła jest też m. in. stara, granitowa kropielnica, obraz Matki Boskiej Leśniańskiej z około połowy XIX wieku, XX-wieczne ławki i konfesjonał.
Przed kościołem, na jego osi, stoi drewniana dzwonnica, zapewne XVIII-wieczna. Na rzucie kwadratu, o konstrukcji słupowo-ramowej i więźbie dachowej z „mnichem”, oszalowana. Ma dwie kondygnacje – w dolnej przejazdowa brama, górna kondygnacja jest węższa, z parami zamkniętych odcinkowo otworów w każdej ścianie. Dzwonnica nakryta jest niskim, namiotowym dachem z wydatnym okapem. Szeroki dach okapowy jest też między kondygnacjami. Oba są blaszane.
Źródła:
1. Katalog zabytków sztuki w Polsce, T. VIII, z. 2 – powiat Biała Podlaska, Warszawa 2006
2. Janusz Maraśkiewicz, Aneta Semeniuk, Drewniane budownictwo sakralne. Powiat Biała Podlaska, Lublin 2001
3. Magdalena Semeniuk, Piotr Semeniuk, 400 lat parafii Witoroż, Międzyrzec Podlaski 2006