In the beginning, the town consisted of two parts «a fortress on the water and a fortress on the hill».
Today, the remains of medieval walls are traceable only on some spots, in the seaward part of the fortification. The walls and towers by the sea, from Forte Mare to Mezaluna, belong to the earliest stage of construction in this area. According to written sources, works on the construction of Herceg Novi began in 1382. However, analyses of the construction technique applied in the lower segments of Mezaluna tower, the part of the wall with two towers and their general form related to the remains by the sea, lead to the conclusion that they had been built in a period well before 1382.
From this location, a transport service to Rose might have been running in the Roman (or later) times, so that it is possible that king Tvrtko used ruined and neglected remains of such a station in order to build his town. We cannot either exclude a possibility that these are the remains of Traiectus.
Other walls, towers and gates are mainly from the Turkish and Venetian times. The Kanli Tower (Bloody Tower) is from the Turkish time, as well as the west and east gates, while Forte Mare originates from later Venetian period.