Obecny kościół w Otroczu p.w. Narodzenia N.M.P wybudowano jako świątynię grecko-katolicką w latach 1872-1874. Po kasacie Unii w 1875 roku zamieniono go na cerkiew prawosławną. Jako kościół parafialny, parafii rzymsko-katolickiej został rekoncyliowany i poświęcony w 1919 roku. Kopuły cerkiewne zdjęto w 1928 roku, dobudowując wieżę i nowy dach.

Podczas II wojny światowej świątynię przekazano Ukraińcom obrządku prawosławnego, którzy stanowili w tym czasie w Otroczu ponad 80% ludności. Do katolików świątynia wróciła w 1945 roku.

Murowany kościół odnowiono zewnątrz i pomalowano w 1997 roku. Wnętrza odnowiono w roku 2000, a w rok później zakupiono nowy dzwon, umieszczony w nowo wybudowanej dzwonnicy . W roku 2002 dokonano renowacji ołtarza głównego.


Po raz pierwszy drewnianą cerkiew otrocką wzmiankowano w źródłach w 1620 r. Należała wtedy do dekanatu unickiego w Szczebrzeszynie. W 1756 r. Jan Zamojski ufundował nową cerkiew drewnianą pod wezwaniem Trójcy Przenajświętszej. Nie wiadomo, jakie były jej losy, jednak na jej miejscu w latach 1872-1874 państwo rosyjskie na własny koszt wzniosło cerkiew murowaną. Od 1875 r. świątynia służyła wiernym obrządku prawosławnego pod zmienionym wezwaniem Різдва Пресвятої Богородиці. W 1919 r. świątynię rekoncyliowano i poświęcono jako kościół pierwszej w historii wsi parafii rzymskokatolickiej.

W 1928 r. rzymscy katolicy, wywodzący się z byłych unitów, pozwolili na demontaż kopuł cerkiewnych, wybudowano w ich miejsce wieżę i pokryto obiekt nowym dachem. W 1942 r. z inicjatywy wiernych wyznania prawosławnego okupacyjna administracja niemiecka pozwoliła odebrać świątynię katolikom i przekazała Ukraińcom obrządku prawosławnego, stanowiącym wówczas Otroczu 80% mieszkańców. Po deportacji ludności ukraińskiej do Ukraińskiej SRR cerkiew znowu stała się własnością katolików, ponownie poświęcono ją w rycie rzymskim 18 marca 1945 r. Proboszczem parafii został ks. Piotr Gąder, który przyczynił się do jej zorganizowania. Obecnie Otrocz zamieszkuje 6 rodzin wywodzących się z dawnej ludności ukraińskiej, które poprzez zmianę wyznania z prawosławnego na rzymskokatolicki uniknęły opuszczenia wsi w 1945 r.

Na stronie internetowej rzymskokatolickiej diecezji sandomierskiej wczesna historia świątyni nie jest wspomniana. Zaczyna się w 1872 r., kiedy zainicjowana została budowa obiektu sakralnego określonego jako „kościół”: „Kościół w Otroczu został wybudowany w latach 1872-1874 jako świątynia greko-katolicka”. Jednak w istocie nie był to kościół, a cerkiew katolickiego obrządku greckiego (unickiego). Na tej samej stronie zmianę własności obiektu unickiego na rosyjski kościół prawosławny ujęto następująco: „W roku 1875 wraz z kasatą Unii przez rząd carski kościół został zamieniony na cerkiew prawosławną” (patrz: http://www.sandomierz.opoka.org.pl/strdiec/parafie.php?p=133).