Parohija Katoličke Crkve u Beodri osnovana je 1796-te, a inicijator je bila grofovska porodica Karačonji. Pod svoje okrilje prima vernike mađare, kao i pridošle nemce, naseljene u dva navrata i to 1795-te i u periodu od 1797-me do 1805-te. Prva Crkva je bila podignura od čerpića, na mestu današnje zgrade Parohije. Kako Historia domus kaže, podigao ju je Bogdan Karačonji, a posvećena je Svetoj Mariji Magdaleni. Tokom sledećih nekoliko decenija spahijski posed se intezivno razvija i Bogdanovi naslednici Laslo i Lajoš 26 aprila 1838 godine osvećuju temelje nove Crkve. Ona postaje porodična grobnica - mauzolej i u kripti ispod oltarskog dela sahranjeno je dvadesetak članova porodice Karačonji. Po predanju, Crkvu krase dva tornja, jer su je podigla dva brata, među kojima je bio prisutan stalni antagonizam ( Stariji Laslo 1849-te podiže sebi dvorac monumentalnih razmera, a malđi Lajoš 1857-me podiže nedaleko od bratovog drugi, još veći ). Cigla za izgradnju Crkve dovožena je iz Velike Kikinde, dok je građa Tisom transportovana iz Erdelja ( Bukovine ) kao i za dve susedne Crkve. Interesantno je da su sve tri Crkve krasile istovetni kapiteli na stubovima - korintski - ali su se samo na Crkvi u Karlovu do danas očuvali. Gradnja Crkve je završena 16 novembra 1841 godine, dok je potpuno opremanje trajalo do 27 novembra 1842-ge, kada je Crkva svečano osvećena. Stariji meštani tvrde da tornjevi sve do XX veka nisu krečeni, već je prvobitno malterisanje bilo izvedeno uz pomoć katrana (?), što je tornjevima sve do prvog celovitog krečenja, davalo tmuran izgled. Ostatak Crkve je spolja redovno krečen u belo. Za razliku od spoljašnjeg izgleda, unutrašnost crkve je u celosti zadržala prvobitan izgled. Majstorski postavljeni prozori u oltarskom delu u potpunosti ukazuju na vrhunskog arhitektu, koji je bogatu štukoderaciju na suptilan način razradio. Glavni oltar, propovedaonica kao i oltar desno od ulaza, naručen je kod bečkog majstora Reisingera, dok je oltar levo od ulaza zbog stilskih različitosti verovatno uradio drugi masjstor. Život trećeg umetničkog stolara Fogaroši Janoša, sudbina je povezana sa Crkvom. Dolaskom u Beodru Stolar počinje da radi sav preostali drveni mobilijar, kako za crkvu, tako i za ostale potrebe u oba dvorca. Ispovedaonice, skamije, klupe u Crkvi, ormani za čuvanje pogrebnog pribora i odeždi u sakristijama, delo su ovog majstora. Kako su se narudžbine stalno umnožavale, tako se boravak u Bedri produžavao, te tu zasniva porodicu...
Članovi grofovske porodice nisu pratili službu sa ostalim vernicima, ve' su za njih iznad sakristija izgrađene posebne lože. One su bile opremljene kožnim foteljama i luksuzno uređenim skamijama, izdignutim na podijumu u visini tri stepenika. Iza loža se mogla sagledatisva lepota Crkve, pratiti služba, a pri tom ostati daleko od pogleda znatiželjnih vernika.
Zanimljivo je da su Karačonjijevi izgradili i opremili Crkvu u potpunosti ( u crkvi se nalazi goblen Bogorodice sa malim Isusom, nastao 1892-ge, a izvezla ga je lično grofica Irma Karačonji ), a jedino je zvona poklonila bogata udovica Lovas Terezija. Za zvona je vezana interesantna priča: sve do 29 oktobra 1917 godine zvona su se oglašavala sa tornjeva. Tog dana su sva zvona rekrivirana i uz zgražanje vernika jednostavno pobacana na plato ispred Crkve. Od sakupljenih komada, negde daleko su izliveni topovi. Tek 1932-ge aprila meseca, Katolička parohija u Beodri kupuje tri nova zvona. Dobrovoljne priloge u novcu i žitu pored vernika katoličke veroispovesti daju i pravoslavni vernici: Cveta Kovačev, Dančika Grujin, Đura i Krasoje Doroslovac. Tadašnji Crkveni odbor donosi odluku da svaki umrli član iz te tri porodice bude besplatno "glašen" i ispraćen na put do groblja, uz zvonjavu zvona. Taj nepisani zakon zadržan je do današnjih dana.
Paroh sa najdužim stažom u beodranskoj Katoličkoj službi je svakako Bottyan Janoš. Za vreme njegovog službovanja ( 1828 - 1878 ) podignuta je nova Crkva i smatra se da je to jedan od najznačajnijih perioda u dvovekovnom životu parohije. Njegovo prisno prijateljstvo sa Pravoslavnim sveštenikom Aksentijem Joanovićem, dedom dr Đorđa Joanovića ( jednim od osnivača Medecinskog fakulteta u Beogradu ) trajalo je više decenija. Sveštenik Battyani je svakodnevno ručavao u gostionici na čošku kod Katoličke Crkve, a kad je postao udovac, tu je redovno ručao i ostareli Joanović. Jednom prilikom zadesio se u gostionici slikar Đorđe Pecić, učenik Kostantina Danila, pa su se likovi velikih prijatelja preselili na platno. Na poleđini slike u ulju, ostalo je zabeleženo da je rad završen 24 februara 1878 godine, kad umire Bottyani, a sledeće i Aksentije.
Još jedna slika na zidu Katoličke Crkve svedoči o prijateljstvu dvojice sveštenika. Odlazeći često u Beč kod sina Karitona, Aksentije se upoznao sa baronom Sinom-Simonom, kod koga mu je sin, inače advokat, bio u službi. Bogati vlastelin, po poreklu cincarin iz Moskopolja, obilato je pomagao Grčku pravoslavnu Crkvu u Beču. Sa beodranskim advokatom Karitonom se okumljuje, krsti mu oba sina, a jednom čak daje svije ime. Prilikom jednog susreta poklanja starom svešteniku dve ikone. Po povratku u Beodru Aksentije zadržava "Bogorodice sa Hristom" ( ulje na drvetu, italo'kritskog porekla ), dok drugu ikonu "Hristova glava na plaštu", rad nepoznatog majstora, poklanja Katoličkoj Crkvi u Beodri...