The earliest mention of Nehaj dates back to 1542. In the 1555 report, which locates the town between Bar and the Paštrovic area, we find information that it was guarded only by two soldiers and a cannoneer at that time. Another report from 1558 states that, in case of need, the town could provide shelter for 900 people. In the earliest preserved engraving of Bar from 1550 the town can be seen in the top left corner. The town is supposed to might have been built in the late 15th century.
The town is extremely inaccessible from all sides but the west one, where the entrance is situated. Next to the entrance gate, where three stages of construction can be discerned, a water cistern was subsequently built. At the highest point on the hill, within the town, a small church of St. Demetrius is situated, having been built before the fortification itself. The town was basically designed for defense by firearms. It has circular towers and numerous loopholes dating from a later period. On almost vertical rocks in the furthest east, a gunpowder magazine is located. The whole south part of the town, which is higher, as well as the part near the entrance gate contain residential objects. These parts could be older than the north one.