Godine 1382. kralj Tvrtko je poceo podizati novi grad na teritoriji župe Dracevice. On ga je nazvao Sv. Stefan ali je grad odmah prozvan Novi i to ime mu je ostalo. Docnije je po Hercegu Stjepanu dobio naziv Herceg Novi. Poslije smrti Tvrtkove 1391. godine Novi je držao Sandalj Hranic sve do 1435. godine, a zatim do 1466. godine Herceg Stjepan. Hercegov sin Vlatko je vec 1475. godine morao braniti grad od Turaka. Krajem 1481. godine Turci su prvi put zauzeli Herceg Novi, i držali su ga dvjesta godina, sa malim prekidima u periodu od 1538-1539. godine, kada su grad osvojili Španci.

Grad se u pocetku sastojao iz dva dijela «tvrdave na vodi i tvrdave na brijegu».

Danas se ostaci srednjovjekovnih zidova mogu vidjeti tek ponegdje na dijelu utvrdenja kod mora. Zidovi i kule prema moru, od Forte Mare preko Mezalune, pripadaju najstarijoj sacuvanoj gradnji na ovome prostoru. Po pisanim izvorima najstarija gradnja u Herceg Novom izvodjena je 1382. godine, medutim, analiza zidanja donjih djelova Mezalune, dijela bedema sa dvije kule i njihov opšti sklop u vezi sa ostacima u moru, navodi na pomisao da su zidani dosta prije 1382. godine.

Možda je sa ove lokacije vršen prevoz do Rosa u rimsko (ili nešto kasnije) vrijeme, pa je kralj Tvrtko koristio razorene i zapustjele ostatke jedne ovakve stanice da izgradi svoj grad. Nije takode iskljuceno ni to da se ovdje radi i o ostacima Traiectus -a.

Ostali zidovi, kule i kapije su uglavnom iz turskog i mletackog vremena. Kanli kula je iz turskog perioda, kao i kapije prema zapadu i istoku, a Forte Mare je iz kasnijeg mletackog perioda.