Budva was first mentioned in the 5th century BC by Sophocles. Pliny describes it as the «orpidum civium Romanorum... Butuanum », while from the period of the great migration of peoples there are no historical data concerning the town.

Budva is said to have been one of the rare antique towns that did not decline at the beginning of the 7th century. According to Emperor Constantine Porphyrogenitus, the Arabs attacked and ravaged the town in AD 840-841, during the Byzantine rule over it. In AD 840, the church of St. Mary de puncta was built, which is evident from the preserved inscription. During 1040s, the district of Cuceva with Budva belonged to Radoslav, the son of prince Vojislav, and following 1078, the district of Grbalj and Budva were put under Bodin's rule. Between 1184 and 1186, Budva belonged to the Nemanjics who held it until the mid 14th century, when it fell under the Balšics' control. From 1392 to 1396, Budva was ruled by Radic Crnojevic and from 1396 to 1398 by Sandalj Hranic. Ðuradj Stratimirovic took Budva away from Sandalj Hranic. Following Ðuradj's death, the Venetians conquered it. In 1403, the Venetians ceded the town to Balša III who held it, with short interruption, until 1419 when it fell to Venice again. Until 1442, when it finally belonged to Venice, Budva was ruled by despot Ðuradj Brankovic. At that time, the archbishop of Zeta held his residence in the Old Budva castle.

Old Budva is situated on a peninsula. It is connected with the mainland on the western side; the citadel – castle of St. Mary – lies on a small rise to the south, while the harbour is in a northerly direction where it has been situated since the earliest times due to its relatively sheltered position.

The castle of St. Mary is situated on a small rise on the rock and since the earliest times it has been used as a fortress. The oldest remains that can be seen today are a portion of the rampart with a gate and parts of the church of St. Mary de Castello, dating from the 12th to 14th century.

The massive walls from the earliest period are relatively thin, and they are (except the ones from the Venetian period) vertical and without escarpments. To the north and east, they had protrusions (merlons) and embrasures (crenelles) set rather low, which were later closed and built onto. The merlons and embrasures between them were from 105 to 110 cm wide, and they probably date from the early Middle Ages or even an earlier period. Most likely, the wall with merlons and crenelles set so low had originally represented a first defensive line, behind which, at a short distance, stood the main rampart, and later, due to the need to expand the town area, this wall was built onto and became the main defensive object. The eastern and partly northern walls have a parapet walkway on consoles dating from the late Middle Ages. Two bigger town gates, on the north and west, contain machicolations, whose remains are also found above the old gate leading to the castle of St. Mary.

Only the Gradenigo tower, which has preserved antique architecture in the core, while its external side was built in the Venetian period, and the west side of the castle have undergone greater alterations.