Usled njegovog izrazito značajnog geografskog i strateškog položaja, istorijski podaci o Petrovaradinu dosežu znatno dublje u prošlost, nego što je to slučaj sa podacima o današnjem Gradu Novom Sadu. Zapravo, u vreme kada se na području Petrovaradina razvija sve značajnije naselje i kada se polaže kamen temeljac za izgradnju današnje tvrđave, preko Dunava, na bačkoj strani, postoje skromne kuće, koje su zajedno činile naselje, pod nazivom Petrovaradinski šanac.
Ako se pođe od duboke prošlosti, arheološki podaci pokazuju da je na području Petrovaradina postojalao paleolitsko naselje iz perioda 50-45.000 godina p.n.e., a da je od perioda neolita (oko 4500 p.n.e.) ovo područje konstantno naseljeno. Dominantan položaj Petrovaradinske stene nad Dunavom i okolinom oduvek je bio interesantan svim narodima koji su se ovde kraće ili duže zadržavali. Tako, prvo zemljano utvrđenje podižu Kelti, koji se na ovim prostorima pojavljuju u IV veku pre nove ere. Zatim se, u I veku pre nove ere, na ovom području pojavljuju Rimljani, koji ovaj važan strateški punkt organizuju kao svoju tvrđavu (Cusum), koju uključuju u provinciju Panoniju. Potom, nastaje period nestabilnosti i Velike seobe naroda, usled kojeg se ovde smenjuju mnogi narodi, kao što su Huni, Ostrogoti, Gepidi, Langobardi, Avari, Franci i Bugari. Tokom srednjeg veka, područje Petrovaradina postaje poprište borbi za prevlast između Vizantije i Mađara, da bi krajem XII veka, Petrovaradin postao deo srednjovekovne Ugarske.
Iz ovog perioda vladavine Ugarske nad ovim prostorima, potiče i prvi zvaničan istorijski dokument koji govori o postojanju naselja na teritoriji današnjeg Petrovaradina. U pitanju je povelja ugarskog kralja Bele IV iz 1237. godine, u kojoj daruje imanja i sela novoj cistercitskoj opatiji u Belakutu (srednjovekovno utvrđenje na lokaciji današnje Petrovaradinske tvrđave). Vremenom je Petrovaradin postajao sve značajnije naselje, pre svega zbog postojanja skele preko Dunava i vašara koji su posećivali trgovci iz čitave Ugarske.
Najveću opasnost po tadašnje stanovništvo Petrovaradina, predstavljali su Turci Osmanlije, čiji je pravac osvajanja išao prema severozapadu. Po osvajanju Beograda i tokom pohoda na Ugarsku i Beč, Turci su 1526. godine osvojili Petrovaradin, čime otpočinje epoha njihove dominacije na ovom prostoru, duga 161 godinu. Tokom turske vlasti Petrovaradin je imao status sedišta nahije i bio je veoma važna strateška tačka, sa dve ključne saobraćanice u to vreme, Dunavom i Carigradskim drumom. Petrovaradin je tom periodu imao oko 200 kuća, a tu se nalazila Sulejman-hanova džamija, a postojale su i dve manje. Tu su bila i skladišta municije, žitni ambari, mnogi dućani, zanatske radionice, škole, amami, kao i drugi objekti osmanlijske arhitekture. U sastavu grada nalazila se i hrišćanska četvrt sa 35 kuća, naseljenih isključivo Srbima.
Krajem XVII veka, odnosno nakon Velikog bečkog rata i nekoliko katastrofalnih poraza turske vojske, Petrovardin i Srem prelaze u sastav Habzburške monarhije, čineći južnu granicu prema Osmanlijskom carstvu. Nastala je potreba da se Petrovaradin, kao strateški važna tačka u odbrani Habzburške monarhije, značajnije utvrdi. Odmah se krenulo sa rušenjem starih turskih objekata i izradom planova za izgradnju moćnog utvrđenja, čiji će osnovni zadatak biti da zaustavi nova osvajanja Osmanlija na severu. Tvrđava je projektovana i izgrađena po čuvenom Vobanovom sistemu, odnosno u skladu sa najsavremenijim dostignućima fortifikacijske škole tog vremena. Kamen temeljac je u ime cara Leopolda I položen 1692. godine, a ovaj ogroman građevinski poduhvat je izgrađen na tri različita, međusobno povezana visinska nivoa čiju su osnovu činili: Gornja tvrđava (na mestu srednjovekovne tvrđave), Donja tvrđava (ili Donji grad u podnožju) i Dvorožni bastion (Hornverk).
Radovi ovakvih razmera, neumitno su doveli do toga da se promeni fizički izgled tadašnjeg Petrovaradina, i bitno su uticali na budući izgled i namenu kuća, zgrada i saobraćajnica. Ovo se naročito odnosi na izgled Donjeg grada koji karakteriše zbijena urbana arhitektura, oblikovana u stambene blokove, sa sačuvanim vojnim, civilnim i sakralnim objektima. Među najstarije sačuvane objekte, spadaju nekadašnji jezuitski samostan i Crkva Sv. Jurja, koja je građena od 1701. godine, zatim franjevački samostan, kasnije prenamenjen u vojnu bolnicu, kao i zgrada komande Tvrđave. Na potesu glavne ulice, smešteni su uglavnom svi nekad najvažniji objekti vojne i civilne uprave, kao i najreprezentativnije stambene kuće visokih oficira i činovnika, građene tokom XVIII veka u stilu baroka. Pored njih, izgrađeni su i mnogi objekti posebne namene, kao što su barutane, kasarne, magazini, pekare, apoteka i gostionice. Od nekoliko kapija koje su sačuvane, posebno su značajne dve monumentalne glavne kapije- Beogradska i Nova kapija.
Tokom izgradnje Tvrđave, odigrala se jedna od najvećih bitaka između Habzburške monarhije i Osmanlijskog carstva, koja je odredila dalje tokove istorije na ovom prostoru. Bitka kod Petrovaradina odigrala se 5. avgusta 1716. godine, u kojoj je mešovitu hrišćansku vojsku predvodio legendarni Eugen Savojski, dok je osmanlijsku vojsku predvodio Damad-Ali paša. Primenivši posebnu ofanzivnu taktiku, Eugen Savojski je uspeo da nadmudri daleko brojniju Osmanlijsku vojsku i spasi Petrovaradin od ponovnog osvajanja. O veličini i značaju ove bitke, govore i mnoge legende koje su se do danas održale među stanovništvom, kao i kasnije podizanje Crkve Snežne Gospe na današnjem izlazu iz Petrovaradina, u znak velike pobede hrišćanske nad muslimanskom vojskom. Nakon ove bitke, stvorena je mogućnost da pod kontrolu Habzburške monarhije dođu čitav Banat i Beograd, a time se i granica između dva carstva pomerila južno od Petrovaradina, čime otpočinje period u kome on gubi prvorazredni strateški značaj.
U okviru Habzburške monarhije, Petrovaradin je imao provilegovan status, a 1783. godine postaje središte Slavonsko-sremske generalne vojne komande, čije stanovništvo aktivno učestvuje u svim vojnim sukobima monarhije širom Evrope. NJegova Tvrđava, postala je jedna od najbezbednijih u čitavom carstvu, sa oko 4000 vojnika i 400 topova.
Nakon završetka Prvog svetskog rata i vojnog poraza Austrougarske monarhije, Petrovaradin ulazi u sastav novoformirane Kraljevine Srba, Hrvata i Slovenaca.
Danas je Petrovaradin, sa svojom Tvrđavom, deo urbanog Novog Sada. Petrovaradin se tokom vremena i sa povećanjem broja stanovnika širio duž davno utvrđenih koridora koji vode prema Tvrđavi. Mnoga manja naselja u okolini Petrovaradina, nose imena koji vode poreklo od toponima iz mnogih bitaka koje su odigravale na području Petrovaradina (Tatarsko brdo, Alibegovac, Vezirac…) Petrovaradinska trvrđava je sredinom 20. veka u potpunosti demilitarizovana, prograšena je istorijskim spomenikom, stavljena je pod zaštitu države i ustupljena za civilnu upotrebu. Na tvrđavi se nalaze Muzej i Arhiv Novog Sada, hoteli i restorani, ateljei i galerije likovnih umetnika, Akademija umetnosti, Planetarijum i mnogi drugi sadržaji.