Older settlements
Human habitation in the territory of present-day Novi Sad has been traced as far back as the Stone Age. Several settlements and necropolises dating to 5000 BC were unearthed during the construction of a new boulevard in Avijatičarsko Naselje. A settlement was also identified on the right bank of the river Danube in present-day Petrovaradin.
In antiquity, the region was inhabited by Celtic tribes, most notably the Scordisci. Celts had been present in the area since the 4th century BC and founded the first fortress on the right bank of the Danube. Later, in the 1st century BC, the region was conquered by the Romans. During Roman rule, a larger fortress was built in the 1st century, named Cusum, and included in the Roman province of Pannonia.
In the 5th century, Cusum was devastated by Hunnic invasions. By the end of the century, the Byzantines had rebuilt the town and called it Petrikon or Petrikov (Greek: Πέτρικον) after Saint Peter. Slavic tribes such as the Severians, the Obotrites and the Serbs (including the subtribes of the Braničevci and the Timočani) settled the region around Novi Sad, mainly in the 6th and 7th centuries. The Serbs absorbed the aforementioned Slavic groups as well as the Paleo-Balkanic peoples of the region.
In the Middle Ages, the area was controlled by the Ostrogoths, Gepids, Avars, Franks, West Slavic groups, again by the Byzantines, and finally by the Hungarians. It was a part of the medieval Kingdom of Hungary from its foundation in 1000 until the Ottoman invasion in the 16th century. Hungarians began to settle in the area, which before that time had been mostly populated by Slavs. The earliest known mention was as the Hungarian variant Peturwarad or Pétervárad (Serbian: Petrovaradin/Петроварадин), derived from the Byzantine variant, found in documents from 1237. That year, several other settlements were mentioned as existing in the territory of modern-day urban Novi Sad.
From the 13th century to the 16th century, the following settlements existed in the urban territory of the modern-day Novi Sad:
on the right bank of the Danube: Pétervárad (Serbian: Petrovaradin) and Kamanc (Serbian: Kamenica).
on the left bank of the Danube: Baksa or Baksafalva (Serbian: Bakša, Bakšić), Kűszentmárton (Serbian: Sent Marton), Bivalyos or Bivalo (Serbian: Bivaljoš, Bivalo), Vásárosvárad or Várad (Serbian: Vašaroš Varad, Varadinci), Zajol I (Serbian: Sajlovo I, Gornje Sajlovo, Gornje Isailovo), Zajol II (Serbian: Sajlovo II, Donje Sajlovo, Donje Isailovo), Bistritz (Serbian: Bistrica). Some other settlements existed in the suburbs of Novi Sad: Mortályos (Serbian: Mrtvaljoš), Csenei (Serbian: Čenej), Keménd (Serbian: Kamendin), Rév (Serbian: Rivica).
An etymology of settlement names reveals that some designations are of Slavic origin, which indicates that the areas were initially inhabited by Slavs, particularly the West Slavs. For example, Bivalo (Bivaljoš) had a large Slavic settlement dating from the 5th–6th centuries. Other names are of Hungarian origin (for example Bélakút, Kűszentmárton, Vásárosvárad, Rév), indicating that the settlements were inhabited by Hungarians before the Ottoman invasion in the 16th century. Some settlement names are of uncertain origin.
Tax records from 1522 show a mix of Hungarian and Slavic names among the inhabitants of these villages, including Slavic names like Bozso (Božo), Radovan, Radonya (Radonja), Ivo, etc. Following the Ottoman invasion in the 16th–17th centuries, some of these settlements were destroyed. Most of the surviving Hungarian inhabitants retreated from the area. Some of the settlements persisted under Ottoman rule and were populated by ethnic Serbs.
Between 1526 and 1687, the region was under Ottoman rule. In 1590, the population of all villages in the territory of present-day Novi Sad numbered 105 houses, inhabited exclusively by Serbs. Ottoman records mention only those who paid taxes, so the number of Serbs who lived in the area (for example, those that served in the Ottoman army) was likely larger than was recorded.