Το Herceg Novi (στα ιταλικά Castelnuovo) δεν είναι καινούργιο, όπως υπαινίσσεται το όνομα του, αλλά μάλλον αρκετά παλιό, καθώς ιδρύθηκε το 1382 στο χώρο ενός χωριού ψαράδων από τον Βόσνιο βασιλιά Στέφανο I, το οποίο είναι και το όνομα της κεντρικής πλατείας αυτής της πόλης . Οι Τούρκοι κατέκτησαν την πόλη το 1482 και παρέμειναν εκεί για δύο αιώνες, με ένα σύντομο ισπανικό παρελθόν. Η πόλη τέθηκε υπό βενετική κυριαρχία το 1687, κατόπιν πέρασε στην Αυστρία-Ουγγαρία. Μετά από αυτό, το Herceg Novi κυβερνήθηκε προσωρινά από τον Ναπολέοντα, τους Ρώσους και τον Μουσολίνι και στη συνέχεια έγινε μέρος της Γιουγκοσλαβίας. Η ιστορία του, αν και όχι στο σύνολό της, βρίσκεται στην πλατεία της. Είναι παραδόξως τετράγωνο, γιατί χτίστηκε σε τυπικό ιταλικό στιλ, με μια υπέροχη ορθόδοξη εκκλησία στη μέση, που περιβάλλεται από φοίνικες. Ανεπίσημα, το όνομα της πλατείας είναι Belavista. Από εκεί η θάλασσα είναι ορατή, καθώς και ένας οθωμανικός πύργος ρολογιού, ένα ισπανικό φρούριο, το καμπαναριό της καθολικής εκκλησίας στο κατώτερο τμήμα της πόλης.
