Podobno narodziny parafii sięgają odległych czasów misji chrystianizacyjnej św. Wojciecha. Parafia Odrzykoń została erygowana w drugiej połowie XIV stulecia. Uposażona została prawdopodobnie już przy lokacji wioski za króla Kazimierza Wielkiego. Istnienie parafii potwierdzone jest w przekazach źródłowych w 1479 r.
Pierwotny, drewniany kościół, p.w. św. Katarzyny, wzmiankowany w 1646 r. został
rozebrany po wybudowaniu nowego kościoła. Obecny kościół murowany, trzynawowy, neogotycki, zbudowany został w latach 1867-1873 przez majstra budowlanego ze Słowacji Jana Klvoszka, kosztem kolatorów Starowieyskich i parafian. Poświęcenie kamienia węgielnego miało miejsce w 1873 r. Uroczystość konsekracji świątyni p.w. św. Katarzyny Dziewicy i Męczennicy i Matki Bożej Różańcowej odbyła się 7 maja 1902 r., a dokonał jej św. bp Józef Sebastian Pelczar.
Wyposażenie wnętrza kościoła jest neogotyckie, wykonane na przełomie XIX i XX w. Kilka obiektów przeniesiono ze starego kościoła m.in.: chrzcielnicę z końca XV w., dzwon z roku 1507 i sygnaturkę z 1536 r. Polichromię wykonał w roku 1904 Karol Popiel. W kościele znajduje się drewniane, późnobarokowe antependium z płaskorzeźbą Ostatniej Wieczerzy, wykonane ok. 1700 r.
Ponadto podziwiać można późnobarokowy feretron w pięknej ramie z dekoracją snycerską, w środku z obrazem Matki Boskiej Różańcowej z Dzieciątkiem Jezus. Podczas działań wojennych II wojny światowej został spalony dach jednej z wież kościelnych. Wtedy tymczasowo ją zabezpieczono z myślą o restauracji w późniejszym czasie, czego dokonano w roku 2011. W prezbiterium kościoła wstawiono ostatnio nowy ołtarz granitowy wraz z ambonką. W bocznej kaplicy założono nowe okna witrażowe.