At the very end of the Bar town area there is a large medieval fort, which for centuries guarded the approach to the Sutomore Plain from the west, defending  the so-called "Gates of Kotor", which is its traditional name. This passage to Sutomore was named after Kotor merchants who used it as as one of the mainland stopping points on the road towards Bar and Ulcinj. Preserved churches from the 14th century also provide evidence of this the centuries-long tradition. These are the churches of St Tekla, St Paraskeva and St Roch, defender of lepers, and in front of St Tekla it still possible to see the marble obelisk displaying a sword and a tournament shield.
Nehaj stand around 12 km north-west of Old Bar, on a rocky hill at an altitude of 230 meters. It was first mentioned in Venetian ddocuments from 1542. Also, one report from 1555 says that the town stood between Bar and Pastrovic. This document also says that it was then guarded only by two soldiers and a gunman, and three years later, it described as a large fort (Castel de Spizza) which could accommodate up to 900 people, if need be.
It is not known when exactly the fort was built, but according to archaeological finds, on the slope beneath the walls it is possibler to find numerous remains from the Iron Age, and the Roman and Byzantine periods, as well as from the time between the 13th and 19th centuries.
Today there is a building which was built during several separate phases. The oldest one, if the church is excluded, cerainly dates from the late medieval period (15th - 16th century), but it is possible to assume, on the basis of archeological material, that the fort is even older. The complex consists of several segments which enabled the presence of people in the strong walls on the inaccessible cliff for a longer period of time. The best, and definitely the oldest, phase is the entrance with a semi-circular gat. Above the entrance, from the outer sid, there is an aedicule,  a small shrine, which is built of wall tiles, demonstrates that there used to be a fresco here, most probably representing St Demetrius, who was the town's patron. to the left of the entrance, there is a large cistern which used to be vaulted. Later defensive systems were added to this late-medieval phase, mostly built for the defences using guns. Therefore today it is possible to distinguish six round towers connected with pathways to the numerous loop-holes and openings for cannons. In the far eastern part, a gunpowder storage room was built during Ottoman times.