Prvý dokument, ktorý hovorí o tom, že v Oľšove bol začiatkom 14. storočia kostol, v ktorom pred rokom 1330 pôsobil farár Václav a od roku 1330 farár Mikuláš bol z procesu medzi jágerským biskupom a ostrihomským arcibiskupom o Toryský dištrikt.
Ďalší dokument hovorí o tom, že kostol už v 15. a aj 16. storočí bol zasvätený apoštolom sv. Šimonovi a Júdovi. V čase reformácie, ako uvádza kronika na fare v Toryse, filiálka Oľšov podľahla viacerým zmenám. Počas reformácie kostol zobrali evanjelici. V roku 1749 bol kostol evanjelikom odňatý, vrátený katolíkom a bol ako filiálka priradený k farnosti v Krivanoch a v roku 1753 k farnosti Šarišské Dravce. Od roku 1823 sa filiálka Oľšov opäť stáva filiálkou farnosti obce Torysa. Vzhľadom na zlý technický stav kostola postaveného pred rokom 1879, ktorý bol postavený na mieste terajšieho kultúrneho domu bol v spomínanom roku postavený nový kostol na pozemku dnešnej stavby rímsko-katolíckeho kostola, ktorý je stále zasvätený k úcte apoštolov svätého Šimona a Júdu. Menšie úpravy, odstránenie organu, oltára, rozšírenie chóru a sakristie boli v tomto kostole prevedené za pôsobenia vdp. Jána Lešku v sedemdesiatych rokoch.
Z kapacitných dôvodov sa v roku 2002 pristúpilo k radikálnej úprave celej stavby kostola. Z pôvodného kostola ostala sakristia, ktorá bola vystavená v roku 1978 a malá časť apsidy so svätými. Loď bola zbúraná a na jej mieste postavená nová v tvare zvonu. V interiéri boli vzácne, starobylé sochy svätých apoštolov Šimona a Júdu citlivo reštaurované. Podobne zo starého kostola bola odborne zreštaurovaná aj krížová cesta.
V kostole sa nachádza aj obraz Najsvätejšieho Srdca Ježišovho od známeho kňaza J. Kendiča, ktorý bol farárom v Kokošovciach. Vo veži sú umiestnené dva zvony zo starého kostola. Menší váži 90 kg. Nesie meno "Urban." Je na ňom nápis: "Ku ucti Božej mile naše krajaňi z Ameriki obetovali. 1923."Väčší váži 160 kg a je na ňom nápis:,, Oľšavské veriaci oferovaly. Ku ucte Božského srdca Ježišovho ku úcte Šimonovy Júdovi. 1936. Obidva zvony uliali bratia Buchnerovci v Košiciach. Kostol a jeho oltár slávnostne konsekroval 8. augusta 2004 Mons. Alojz Tkáč, košický arcibiskup - metropolita.
