Ulcinj was mentioned by Tit Levy (Titus Livius) and Pliny the Elder at the end of the old era and in the 1st century AD. Pliny states that Olcinium was originally called Colchinium and describes it as oppidum civium Romanorum. Ptolemy, in the 2nd century AD, refers to the town as ????????. Emperor Constantine Porphyrogenitus mentions Ulcinj as Helcynio, while papal bulls from the 11th and 12th centuries document it under various names (Ulcini, Dulcinium, Licini, Dulcignum). During the time of Duke Vladimir, emperor Samuilo (976-1014) was trying in vain to besiege Ulcinj. Nemanja took it in 1183. In the 13th century, Ðuradj, the son of king Vukan, held his court in Ulcinj, as well as queen Jelena's sister Mary, referred to as «domina Ulcinii». Jelena of Anjou, the wife of king Uroš I, retired to Ulcinj after becoming a widow. The widow of emperor Dušan, also called Jelena, ruled Ulcinj for some time. Ðuradj Stracimirovic Balšic (1385-1403) held his court in Ulcinj and even died there. Following his death, the Venetians took Ulcinj from his son Balša III to give it back only in 1412. Following the death of Balša III (1421) and struggles over the throne between his heir Stefan Lazarevic and the Venetians, the latter took Ulcinj in 1423. In 1571, the Turks finally seized the town.

The town is situated on a big rock whose lowest parts lie on the very coast. A citadel is located at the highest point, being inaccessible from all sides but the south. The town has two gates, the one in the lower part, accessed from the sea, and the one in the upper part, accessed from the land. The earliest remains of a Greek-Illyrian fortification have been discovered in the Citadel. The foundations of a smaller church in the lower town belong to the 9th century. There are numerous remains from the high Middle Ages: a portion of the wall around the Citadel, a square tower and a portion of the wall near the sea, as well as the inner side of the upper gate. The remains of a bigger church in the lower town date from the 13th century. Among the church objects from the Middle Ages we can also include the remains found under an octagonal Turkish gunpowder magazine, an object near the Citadel, probably used as a bishop's residence, containing fragments of fresco painting in the cellar, as well as one bigger building with arcades on the side facing the sea, which might have been a town lodge or a ducal palace. Residential buildings from this period have been scarcely preserved in upper floors, they are mainly found in the ground levels of the existing buildings. The greatest portions of the town walls, both towards the sea and near the Citadel, are from the Venetian time, together with a kind of a donjon tower, the so-called «Balšic Tower», which might date from previous period. Some military objects in the Citadel and the Upper town, portions of the walls, gunpowder magazines and numerous residential buildings date from the Turkish time.