Opština Petrovaradin (latinski Varadinum Petri, nemački Peterwardein, mađarski Pétervárad) je ne samo od 1928. godine sastavni deo Novog Sada, već i njegov neodvojivi simbol. Ona se nalazi na desnoj obali Dunava, a time već u Sremu. Oba gradska dela su u svojoj istoriji bila povezana pontonskim mostovima i trima stabilnim mostovima. Dva od njih, uništena tokom NATO-bombardovanja 1999. godine, su u međuvremenu opet izgrađena.

Na jednoj visoko strčećoj steni planinskog lanca Fruške Gore, pod kojom Dunav čini jednu od svojih najvećih krivina, se oduvek nalazilo jedno utvrđenje. Nakon oslobođenja tog srednjovekovnog utvrđenja od Osmanlija, general le Kroj (le Croy) 1692. godine polaže kamen temeljac za izgradnju jedne nove tvrđave, koja postoji još i danas.

Nakon pobede nad Osmanlijama, 5. avgusta 1716. godine, vojskovođa princ Eugen Savojski (Prinz Eugen von Savoyen) po legendi poklanja crkvi Bezgrešnog začeća Blažene Device Marije, koja se nalazila u neposrednoj blizini bojišta, sliku pomoćnice i zaštitnice Gospe Snežne, Bogorodice sa detetom. Ta slika će postati predmetom velikog poštovanja. Njoj će biti pripisivane čudotvorne moći. Eugen Savojski je zaslužan i za izgradnju Petrovaradinske tvrđave, jednog od najvećih utvrđenja u Evropi. Ona se prostire na jednoj površini od 112 hektara. Sa njenim zidinama, rovovima i bedemima, njenim podzemnim hodnicima sa ukupnom dužinom od 16 kilometara, čija je izgradnja trajala 80 godina, ona postaje simbol pobede nad Osmanlijama, kao i građevinske umetnosti austrijske vojne arhitekture. Sa svojim atraktivnim gornjim delom sa visoko stčećim bedemima i tornjem sa satom, koji pokazuje u pravcu Dunava, sa oficirskim paviljonom i jednom dugačkom kasarnom, u kojoj se trenutno nalaze jedan hotel i Istorijski arhiv grada Novog Sada, tvrđava predstavlja jednu pravu turističku atrakciju. Petrovaradinska stena nudi odličan pogled na Novi Sad i dobar deo Bačke.

Tvrđava je danas sedište brojnih kulturnih ustanova, kao što su Gradski muzej, Gradski arhiv i Atelje 61, koji raspolaže jednom izuzetnom zbirkom tapiserija savremenih umetnika. U tvrđavi se nalaze i Akademija umetnosti i više umetničkih ateljea. Donji grad sa katoličkom crkvom Sv. Đorđa (hl. Georg) važi kao izuzetan spomenik barokne arhitekture u ovoj oblasti. Izvan zidina se nalazi naselje Petrovaradin. Među vojnicima i civilima Petrovaradina, koje su najvećim delom činili Hrvati, je, pored Mađara i Židova, bilo i dosta Nemaca.