Petrovaradin i Petrovaradinska tvrdjava su neraskidivo povezani sa Katolickom crkvom na tim prostorima. Naime, kralj Bela IV je 1235. godine na to podrucje naselio monahe cistercite, iz starog manastira Troafonten iz pokrajine Sampanj u Francuskoj. Oni su na mestu danasnje Tvrdjave podigli opatiju, koju su po svom kralju i izvoru vode koji je tu postojao prozvali Belakut (Belin studenac). Dve godine kasnije, Bela IV je opatiji darivao posede u Sremu i Backoj, Petrovaradin sa tamosnjom kraljevskom palatom i svim bogatstvima, i tri sela. Cisterciti su tako dobili materijalnu osnovu da na tom mestu izgrade opatiju, utvrdjeni zamak koji je preteca danasnje Tvrdjave i dali joj ime Petrovaradin. Dalji razvoj Tvrdjave podstakao je 1247. godine papa Inocentije IV koji je pismom molio ovdasnje nadbiskupe da zastite zemlju od provala Tatara.

Nakon 1526. godine, posle pada Tvrdjave u turske ruke, pa narednih 161 godinu u Pertovaradinu su se nalazile i tri dzamije.

Pola veka nakon oslobodjenja od Turaka 1691. godine, od 1746. do 1773. godine u Petrovaradinu je bilo sediste Sremske katolicke biskupije. Posto je Petrovaradin bio izuzetno znacajno vojno naselje Austrougarske carevine, bio je i pod jakim uticajem Vatikana i Katolicke crkve. Usled toga u Petrovaradinu, tj. naselju nastalom oko Tvrdjave, mogli su da se naseljavaju samo stanovnici katolicke vere, iako je medju vojnicima u Tvrdjavi bilo dosta pripadnika drugih veroispovesti. Ova cinjenica uticala je da u Petrovaradinu do danas, izuzev u jednom slucaju, postoje iskljucivo katolicke crkve:

1. Crkva Sveti Rok, u Preradovicevoj ulici br.160, koja je sagradjena 1808. a obnovljena 1961. godine;
2. Crkva Blazene device Marije (Gospa snezna) na Tekijama, sazidana na mestu velike bitke u kojoj je Austrougarska vojska pod komandom Eugena Savojskog pobedila Tursku vojsku 1716. godine, obnovljena je 1881. godine.

U donjem gradu Petrovaradinske tvrdjave od 1699. do 1772. godine gradjen je samostan Svetog Franje, koji je sluzio svojoj nameni samo do 1786. godine. Te godine ga je car Josip II ukinuo, iselio fratre i pretvorio u vojnu bolnicu, koja i danas sluzi toj nameni.

Od 1924. godine u Petrovaradinu je postojala i pravoslavna crkva Svetog Apostola Pavla sagradjena u okviru vojne bolnice za potrebe vojnika pravoslavne vere. Ona je sluzila svojoj nameni sve do 1941. godine kada je pretvorena u skladiste lekova za potrebe vojne bolnice. Pocetkom 1991. godine ju je Jugoslovenska narodna armija vratila Srpskoj pravoslavnoj crkvi. Posto je ova crkva jedno vreme koriscena kao apoteka u njoj je instalirano i grejanje, koje je tu i ostalo posle vracanja objekta Srpskoj pravoslavnoj crkvi. Tako je ovo sada jedina crkva u nasoj zemlji koja ima centralno grejanje.