Историјски налази свједоче о постојању Петроварадина још у римским временима. На стјеновитим обронцима Фрушке горе било је римско утврђење Cusum.У раном средњем вијеку Петроварадин је припадао Византији.
У другој половини XII вијека имао је видну улогу у ратовима између Византије и Угарске. Мађарски краљ Бела IV поклонио је 1237. године Петроварадин цистерцитском манастиру Укурду, који је тада прозван Белафонс.
После татарске најезде (1247-1252) Цистерцити су ради одбране саградили утврђење. Постоје претпоставке да је у другој половини XIII вијека, за вријеме краља Драгутина Немањића, који је владао дијелом Срема, Петроварадин припадао српској држави.
У Петроварадину је 1463. године одржан сабор на којем је склопљен уговор о одбрамбеном савезу између Угарске и Венеције против Отоманске империје, али је султан Сулејман Величанствени ипак, освојио Петроварадин 1526. године.
Петроварадин је био под турском влашћу преко 160 година, све до 1687. када га је узела аустријска војска. Турци су га 1694. године опсиједали, али без успјеха. Последњи пут су га Турци покушали да освоје под командом великог везира Али-бега, aли их је потукла војска под командом Еугена Савојског, 5. августа 1716. кад је изненада у сред љета пао снијег.
На мјесту старе тврђаве на узвишици високој 40 метара од 1692 године почиње градња највеће фортификације по Вобановом плану у Аустријском царству и прва фаза градње траје до 1726, године, а друга од 1753. до 1780. године.
Била је то једна од најимпресивнијих грађевина војне архитектуре свог доба у Европи.
"Гибралтар на Дунаву", како су га звали, најинтензивније се градио за време владавине царице Марије Терезије. Тврђава заузима површину од 112 хектара са јединственим системом подземних ходника дужине 16 километра.
Почетком Првог српског устанка у арсеналу Петроварадинске тврђаве су монтирани први устанички топови који су преко Срема кријумчарени у Мачву.
У Тврђави је након пропасти устанка био интерниран Карађорђе са својим војводама. У време Буне 12. јуна 1849. године, мађарска војска са Тврђаве је бомбардовала Нови Сад, који је запаљен и готово цио уништен.
Петроварадин је атрибуте града добио пре Новог Сада, тако је зидана канализација са Тврђаве до Дунава завршена 1725. године а у Новом Саду је прва канализација саграђена 1880.
Поштанске пошиљке су ишле преко петроварадинске поште у 18. веку, а у Новом Саду је пошта почела да ради 1853. године. Телеграф је у Петроварадину уведен 1853, а у Новом Саду 1857. године.
